algo-aha

旋转数组中找值t

• https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

旋转数组对半分后，一半是有序数组、一半是旋转数组（两半都是有序数组的情况也符合讨论，因为有序数组是特殊的旋转数组）。这“一半是有序数组”的条件是该利用的。见ctci p399

怎么判断哪一半是有序数组？比较x[mi]和x[hi]。用mi和hi比较更健壮，因为mi一定!=hi（len>=2时）。若用lo和mi比较，因为mi向下取整，mi可能==lo，从而使判断if (x[lo]<x[mid])被绕过，会增加边界情况复杂度。

bool search(vector<int>& nums, int target) {
    // 旋转数组对半分后，一半是有序数组、一半是旋转数组
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mi = lo + (hi - lo) / 2;
        if (nums[mi] == target) return true;
        
        if (nums[mi] < nums[hi]) { // 右半有序
            if (nums[mi] < target && target <= nums[hi]) {
                lo = mi + 1;
            } else {
                hi = mi - 1;
            }
        } else if (nums[mi] > nums[hi]) { // 左半有序
            if (nums[lo] <= target && target < nums[mi]) {
                hi = mi - 1;
            } else {
                lo = mi + 1;
            }
        } else { // nums[mi] == nums[hi]
            hi--;
        }
    }
    return false;
}

旋转数组的最小值

• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

int findMin(vector<int>& nums) {
	// 旋转数组对半分，一半旋转一半有序，最小值在旋转那一半
	const int N = nums.size();
	int lo = 0, hi = N - 1;
	while (lo < hi) { // len([lo..hi])>=2
		int mi = lo + (hi - lo) / 2;
		// 由于mi向下取整，可能mi==lo，
		// 若用if (nums[lo] < nums[mi])，当mi==lo时这个if将被绕过
		// 用mi和hi就没这个问题，mi!=hi
		if (nums[mi] > nums[hi]) { // 右半旋转，且m位置不是min
			lo = mi + 1;
		} else { // 左半旋转
			hi--;
		}
	}
	return nums[lo];
}