Problem explanation:
Initial Sorted array: [0,1,2,4,5,6,7] After rotation it becomes [4,5,6,7,0,1,2]. Target = 0 Index = 4 [as array index starts from 0]
This problem can be solved in 2 ways:
- Linear Search
- Modified Binary search
-
Linear search:
In this solution, we search the element one by one and return the index. But come on, we shall give the interviewer the 2nd solution.
-
Modified Binary search
We can solve this by using a modified binary search.
In Binary search, we divide the sorted array into 2 parts. And change the lower index and higher index according to the mid element.
The same solution cannot be applied here, because the array is not sorted. But we know that in a divided array there is always a half that is sorted. Hence we need to find whether the number is in the sorted part or in the rotating part.
We use the below code to achieve the same:
int binary_search_modified(vector<int>& array, int target) { int low = 0; int high = array.size()-1; while (low <= high) { 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; }
Let us understand with an example
Input: 4, 5, 6, 7, 0, 1, 2 Target = 0 Pass 1: low = 0 high = 6 while(0 <= 6) true mid = (6-0) / 2 + 0 = 3 if array[3] == target ? false if(array[3] < array[6]) => (7 < 2) ? false else case if(array[0] <= target && target < array[3]) => (4 <= 0 && 0< 7) false else case low = mid + 1 => 3 + 1 >4
Pass 2: low = 4 high = 6 while (4 <= 6) true mid = (6 - 4)/2 + 4 = 5 if(array[5] == target) ? false if(array[5] < array [6]) => (1 < 2 ) true if(array[5] < target) && (target <= array[6]) => (1<0 && 0<=2) false high = mid -1 => 5 - 1 = 4
Pass 3: low = 4 high = 4 while(4 <= 4) mid = (high - low)/ 2 +low => 4 if array[4] == target => true return 4
Solution in C++
/* * File : search_in_sorted_array.cpp * Purpose : Search the target element in a sored array, but reversed at an index */ #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) { 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(4); array.push_back(5); array.push_back(6); array.push_back(7); 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:
4 5 6 7 0 1 2 The target = 0 found at index = 4
List Of Tutorials available in this website:
No Responses