二分法问题总结

二分法问题总结

1. leetcode33 搜索旋转排序数组

解题：( 时间复杂度O(logN)，空间复杂度O(1) )

二分法，找到中间值，不断缩小搜索范围，下一搜索范围是中间值左侧或右侧

旋转排序数组的特点是局部有序，中间值左/右，有一侧一定是有序的，通过有序区间可以判断出target值是否在该区间内，如果不在，则在另外区间---> 这样就缩小了搜索范围

该题目需要注意数组中元素个数为0或1。

下图为有序数组旋转后与中间值的关系图（无序的一侧一定不满足最左端的值<=中间值）

class Solution {
public:
    int search(vector& nums, int target) {
        int n = nums.size();
        if (!n) return -1;
        if (n==1) {
            return nums[0]==target?0:-1;
        }
        int l = 0;
        int r = n-1;
        while(l <= r) {
            int mid = l+(r-l)/2;
            if (target==nums[mid]) return mid;
            if (nums[0] <= nums[mid]) { // 左侧有序
                if (target>=nums[l] && target<=nums[mid]) {
                    r = mid-1;
                } else {
                    l = mid+1;
                }
            } else {
                if (target>=nums[mid] && target<=nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1; 
                }
            }
        }
        return -1;
    }
};