Given a sorted array of n integers that has been rotated an unknown number of times, give an O(logn) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order.

EXAMPLE:

Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)

Output: 8 (the index of 5 in the array)

**My initial thoughts:**

Using the idea of binary search, we can find the breakpoint (e.g. 1 in the input) of the array in . Then we divide the original array into two sorted sub-arrays. We can then do regular binary search for both of them in . So altogether we still have running time.

**My initial codes:**

public static int find(int[] array, int search) {
int i = 0;
int j = array.length - 1;
int mid;
do {
mid = (i + j) / 2;
if (array[mid] < array[mid - 1])
break;
else {
i = mid + 1;
}
} while (i <= j);
int leftIndex = binarySearch(array, 0,
mid - 1, search);
if (leftIndex != -1)
return leftIndex;
else
return binarySearch(array, mid,
array.length - 1, search);
}
private static int binarySearch(int[] array,
int i, int j, int search) {
int mid;
do {
mid = (i + j) / 2;
if (array[mid] == search)
return mid;
else if (array[mid] < search) {
i = mid + 1;
} else {
j = mid - 1;
}
} while (i <= j);
return -1;
}

**Solution:**

public static int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) { // sorted sub-array
// regular binary search
if (x > a[m]) {
l = m + 1;
} else if (x >= a[l]) { // x might fall
// before the smallest element
u = m - 1;
} else {
l = m + 1;
}
}
// implicit condition: a[l] > a[m]
else if (x < a[m]) // left part
u = m - 1;
else if (x <= a[u]) // right part
l = m + 1;
else
u = m - 1;
}
return -1;
}

Comments:

Need to consider all the possible relations of a[l], a[m], a[u] and x.

### Like this:

Like Loading...

*Related*

ekayrakli

Mar 31, 2012@ 10:50:08I might be being too picky but, in your code shouldn’t you pass the original array and start and end indexes to binarySearch method, instead of getting the copy of a range of the array? I mean, if you use copyOfRange(), whose complexity is most probably O(n), wouldn’t that make your overall complexity O(n)?

Runhe Tian

Mar 31, 2012@ 10:52:59That’s a very good insight. Thanks so much!

Shyam

Jun 10, 2012@ 09:27:36can you tell me what’s wrong with your initial solution apart from the one pointed out by ekayrakli?

Runhe Tian

Jun 10, 2012@ 12:06:05It’s just a bit more complex compared to the solution.

beewithus

Jan 14, 2014@ 02:56:25Well written facts. It can be precious to anyone who else employess this, including my family. Keep carrying out what you are doing – beyond doubt i’m going take a look at more blogposts.