SearchinRotatedSortedArray

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution

既然是有序，自然想到二分搜索, 和Find Minimum in Rotated Sorted Array类似:

初始化s = 0, t = n - 1:

• 若a[s] < a[t], 比如1 2 3 4 5,则整个列表有序，直接二分搜索即可.

• mid = s + ((t - s) >> 1), 若a[mid] == key, 返回mid，结束

• a[mid] < a[t], 比如5 1 [2] 3 4或4 5 [1] 2 3, 则右边一定是有序的:

  • 若a[mid] < key <= a[t], 二分搜索右边部分即可
  • 否则搜索左边， t = mid - 1

• a[mid] > a[t], 比如3 4 [5] 1 2 或者 2 3 [4] 5 1, 则左边一定是有序的:

  • 若a[s] <= key < a[mid], 二分搜索左边部分
  • 否则搜索右边，s = mid + 1

首先实现二分搜索:

int binarySearch(int *a, int s, int t, int key)
{
	while (s <= t) {
		int mid = s + ((t - s) >> 1);
		if (a[mid] == key)
			return mid;
		if (a[mid] > key)
			t = mid - 1;
		else
			s = mid + 1;
	}
	return -1;
}

然后使用以上算法实现:

int search(int *a, int n, int key)
{
	int s = 0, t = n - 1;
	while (s <= t) {
		if (a[s] < a[t])
			return binarySearch(a, s, t, key);
		int mid = s + ((t - s) >> 1);
		//printf("s = %d, t = %d, mid = %d\n", s, t, mid);
		if (a[mid] == key)
			return mid;
		if (a[mid] < a[t]) {
			if (a[mid] < key && key <= a[t])
				return binarySearch(a, mid + 1, t, key);
			else
				t = mid - 1;
		} else { // a[mid] > a[t]
			if (a[s] <= key && key < a[mid]) // 若key 在s和mid之间
				return binarySearch(a, s, mid - 1, key);
			else
				s = mid + 1;
		}
	}
	return -1;
}

扩展

1. Find Minimum in Rotated Sorted Array

2. Find Minimum in Rotated Sorted Array II