ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

you are given an sorted array with repeated elements that is rotated at some point, return true or false if you find the key element in C++

prodevelopertutorial September 4, 2018
Example 1:

Input: nums = [2,5,6,0,0,1,2], key = 0
Output: true

Before solving this problem, please look at the similar problem. Search in Rotated Sorted Array.

We achieve this by below 2 lines:

while (low < high && array[low] == array[low + 1]) low++; // skip duplicates from the left
while (high > low && array[high] == array[high - 1]) high--; // skip duplicates from the right

Solution in C++

#include<iostream>
#include<vector>
using namespace std;
 
int binary_search_modified(vector<int>& array, int target) 
{
    int low = 0;
    int high = array.size()-1;
 
    while (low <= high) 
    {
    	while (low < high && array[low] == array[low + 1]) low++; // skip duplicates from the left
        while (high > low && array[high] == array[high - 1]) high--; // skip duplicates from the right
        
        int mid = ( high-low )/2 + low;
        if (array[mid] == target)
            return mid;
 
        if (array[mid] < array[high]) 
        {
            if ( array[mid] < target && target <= array[high])
                low = mid + 1;
            else
                high = mid - 1;
        } 
        else 
        {
            if(array[low] <= target && target < array[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
    }
    return -1;
}
 
int main()
{
 
    vector<int> array;
 
    array.push_back(2);
    array.push_back(5);
    array.push_back(6);
    array.push_back(0);
    array.push_back(0);
    array.push_back(1);
    array.push_back(2);
 
    int target = 0;
 
 
    for (int i = 0; i < array.size(); i++)
    {
        cout <<array[i] << " ";
    }
    cout<<endl;
 
 
    int index = binary_search_modified (array, target);
    
    if (index)
    {
        cout<<"The target = "<<target <<" found at index = "<< index<<endl;
    }
    else
    {
        cout<<"Target not found"<<endl;
    }
 
}

Output:

2 5 6 0 0 1 2
The target = 0 found at index = 3

 

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io