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;
	}

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

Advertisements

5 Comments (+add yours?)

  1. ekayrakli
    Mar 31, 2012 @ 10:50:08

    I 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)?

    Reply

  2. Shyam
    Jun 10, 2012 @ 09:27:36

    can you tell me what’s wrong with your initial solution apart from the one pointed out by ekayrakli?

    Reply

  3. beewithus
    Jan 14, 2014 @ 02:56:25

    Well 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.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: