[LeetCode]Search in Rotated Sorted Array

证明，对于[lo, mid]和[mid,hi]两个区间，至少有一边是sorted的：

• pivot在mid时，pivot右边都是sorted的，所以[mid,hi]一定是sorted的
• pivot在[lo, mid)，pivot右边都是sorted的，所以[mid,hi]一定是sorted的
• pivot在(mid, hi]，pivot左边都是sorted的，所以[lo,mid]一定是sorted的

所以我们每次判断的时候，能一定能判断半边是sorted的，如果target在这个区间里，去这个区间找。否则去另外一个区间。

代码如下：

	public class Solution {
	public int search(int[] A, int target) {
	if (A == null)
	return -1;
	int len = A.length;
	int lo = 0, hi = len - 1;
	while (lo <= hi) {
	int mid = lo + (hi - lo) / 2;
	if (A[mid] == target)
	return mid;
	if (A[mid] >= A[lo]) {
	if (target >= A[lo] && target < A[mid])
	hi = mid - 1;
	else
	lo = mid + 1;
	} else {
	if (target > A[mid] && target <= A[hi])
	lo = mid + 1;
	else
	hi = mid - 1;
	}
	}
	return -1;
	}
	}

view raw search in rotate sorted array v-1.java hosted with ❤ by GitHub

也可以在判断的时候顺便判断target是不是在lo或者hi，找的的话直接return。不过这样做也不会对时间有多大的影响，个人更习惯第一种写法。代码如下：

	public class Solution {
	public int search(int[] A, int target) {
	if (A == null)
	return -1;
	int len = A.length;
	int lo = 0, hi = len - 1;
	while (lo <= hi) {
	int mid = lo + (hi - lo) / 2;
	if (A[mid] == target)
	return mid;
	if (A[lo] == target)
	return lo;
	if (A[hi] == target)
	return hi;
	if (A[mid] >= A[lo]) {
	if (target > A[lo] && target < A[mid])
	hi = mid - 1;
	else
	lo = mid + 1;
	} else {
	if (target > A[mid] && target < A[hi])
	lo = mid + 1;
	else
	hi = mid - 1;
	}
	}
	return -1;
	}
	}

view raw search in rotated array v-2.java hosted with ❤ by GitHub