LeetCode —— 二分查找

lalala / 2023-08-21 / 原文

33. 搜索旋转排序数组

翻转点在前半部分 nums[mid]<=nums[low]
- 而后半部分是单调递增的，比较好判断。可以判断 nums[mid] < target <= nums[high] 去后半部分
- else 去后半部分
翻转点在后半部分 nums[mid]<=nums[low]
- 而前半部分是单调递增的，比较好判断。可以判断 nums[low] <= target < nums[mid] 去前半部分
- else 去前半部分

class Solution {
    public int search(int[] nums, int target) {

        int low =0;
        int high = nums.length-1;
        // 注意条件是 low<=high
        while(low <= high) {
            // [3,1] target 是 1 的情况，如果这里没有 +1,low,mid是0，那high=mid-1就是-1了
            int mid = (low+high+1)/2;
            if (target == nums[mid]) {
                return mid;
            }
            // 翻转点在前半部分。后半部分是单调递增的
            if (nums[mid] <= nums[low]) {
                // 后半部分是单调递增的。这里是去后半部分的情况
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid+1;
                }
                else {
                    high = mid-1;
                }
            }
            // 翻转点在后半部分+正好在中点。前半部分是单调递增的。
            else {
                // 前半部分是单调递增的。这里是去前半部分的情况
                if (target >= nums[low] && target< nums[mid]) {
                    high = mid - 1;
                }
                else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}