Modified binary search
What is modified binary search problem
Given a sorted array of (n) integers that has been rotated an unknown number of times. Give a log(n) algorithm that finds an element in the array. Assume the array has no duplicates.
Modified binary search algorithm
You need to use a modified binary search method. The trick is to play with the lower and upper array indexes. Binary search in the normal case examines the middle element. If the middle element is equal to the element we are looking for we just return the middle element. If the element that we are looking for is greater than the middle element then we search the right half of the array otherwise we search the left half. This can be accomplished either recursively or by iteration. In our case where the array has been rotated we can not simply search the right or left halves of the array because the order of the elements is not maintained because of the rotation. Consider the following example A = {7, 8, 9, 1, 2, 3, 4, 5, 6} as you can see {7, 8, 9} and {1, 2, 3, 4, 5, 6} are both in order however the transition between the two breaks the order. Let us define some variables:
|
1 2 3 4 5 |
l: lower array index v: value at which the order of the array elements changes x: element we are looking for m: middle element u: upper array index |
Notice that no matter how many times we rotate the array we will have one of the following scenarios
The following three cases where x to the left of m
|
1 2 3 |
l v x m u l x v m u l x m v u |
The following three cases where x to the right of m
|
1 2 3 |
l m x v u l m v x u l v m x u |
if none of the above six cases is applied then the array was not rotated. In that case normal binary search can be applied.
Modified binary search in c
Here is a sample code in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
//Includes #include <iostream> using namespace std; //Function prototype int Search (int [], int, int, int); //Main function void main() { //Sample array int a[] = {7,8,9,1,2,3,4,5,6}; //Search for element cout << "find = " << Search(a, 0, 8, 7) << endl; } //Search function receives array, lower index, //upper index and search key x int Search (int a[], int l, int u, int x) { //Loop as long as the element is not found while (l <= u) { //Index of the middle element int m = (l + u) / 2; //Return index of the element if it is found if (x == a[m]) return m; //The first 3 cases where x to the left of m if ((x <= a[m] && a[m] <= a[u] && a[u] <= a[l]) || (a[m] <= a[u] && a[u] <= a[l] && a[l] <= x) || (a[u] <= a[l] && a[l] <= x && x <= a[m])) { u = m - 1; } //The second 3 cases where x to the right of m else if ((a[u] <= a[l] && a[l] <= a[m] && a[m] <= a[x]) || (x <= a[u] && a[u] <= a[l] && a[l] <= a[m]) || (a[m] <= x && x <= a[u] && a[u] <= a[l])) { l = m + 1; } //In case of 0 rotations perform regular binary search else if (x > a[m]) { l = m + 1; } else { u = m - 1; } } return -1; } |
Please use the comments section below for feedback and questions. Thanks for visiting.
About Author
Mohammed Abualrob
Software Engineer @ Cisco