## Search for an element in a rotated array

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 $O(\log n)$. Then we divide the original array into two sorted sub-arrays. We can then do regular binary search for both of them in $O(\log n)$. So altogether we still have $O(\log n)$ 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;
}

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

__ATA.cmd.push(function() {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```