讨论/《二分查找》 - 搜索旋转排序数组/
《二分查找》 - 搜索旋转排序数组
共 11 个回复
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[left]<=nums[mid])
            {
                if(target<nums[mid]&&target>=nums[left])
                    right=mid-1;
                else
                    left=mid+1;
            }
            else
            {
                if(target<=nums[right]&&target>nums[mid])
                    left=mid+1;
                else
                    right=mid-1;
            }
        }
        return -1;
    }
};
10

二分查找找断点,断点两侧皆为单调区间,便可在区间内二分查找目标值。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 1. 找断点
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[left]:
                left = mid
            else:
                right = mid
        # 2. 在两个单调区间[0, left], [left + 1, last]内找目标值
        leftFound = self.binarySearch(nums, 0, left, target)
        rightFound = self.binarySearch(nums, left + 1, len(nums) - 1, target)
        if leftFound is not None:
            return leftFound
        if rightFound is not None:
            return rightFound
        return -1
    
    def binarySearch(self, nums, left, right, target):
        while left <= right:
            mid = (left + right) // 2
            if target < nums[mid]:
                right = mid - 1
            elif target > nums[mid]:
                left = mid + 1
            else:
                return mid
        return None
4

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1

        left = 0
        right = end

        while left <= right:
            middle = left + ((right - left) >> 1)
            if nums[middle] == target:
                return middle
            if nums[middle] >= nums[start]:
                if target < nums[middle] and target >= nums[start]:
                    right = middle -1
                else:
                    left = middle + 1

            elif nums[middle] < nums[start]:
                if target > nums[middle] and target <= nums[end]:
                    left = middle + 1
                else:
                    right = middle - 1
                    
        return -1



1

这个找断点是O(n)的,需要把找断点也弄成log

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 先找到两个递增子数组个分割点
        int breakPoint = -1;
        int l = 0, r = nums.size() - 1;
        while ( l < r ) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        // 如果 nums[l] > nums[0] 说明整个数组都是递增的此时分割点置为最大下标
        if ( nums[l] > nums[0] )  breakPoint = nums.size() - 1;
        else breakPoint = l;
        // 此时答案在分割点之前不包括分割点,但任然需要包括分割点
        if (target >= nums[0]) {
            l = 0, r = breakPoint;
            while ( l < r) {
                int mid = l + r >> 1;
                if ( nums[mid] >= target) r = mid;
                else   l = mid + 1;
            }
            
        }else {// 答案在分割点之后(包括分隔点)
            l = breakPoint, r = nums.size() - 1;
            while ( l < r ) {
                int mid = l + r >> 1;
                if ( nums[mid] >= target) r = mid ;
                else   l = mid + 1;
            }
        }
        // cout << l << endl;
        if (nums[l] == target) return l;
            else return -1;
    }
};
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        lo, hi = 0, len(nums)

        while lo < hi:
            mid = lo + (hi - lo) // 2
            # mid, pivot, target
            if nums[mid] >= nums[0] > target:
                lo = mid + 1
            elif nums[mid] < nums[0] <= target:
                hi = mid
            elif nums[mid] > target:
                hi = mid
            elif nums[mid] < target:
                lo = mid + 1
            else:
                return mid
        return -1

C++ 二分法求解

class Solution {
public:
    int BinarySearch(vector<int> &nums, int l, int r, int target) {
        int mid;
        while (l < r) {
            mid = l + (r-l >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return nums[l] == target ? l : -1;
    }

    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1, mid;
        // 二分查找最小值下标
        while (l < r) {
            mid = l + (r-l >> 1);
            if (nums[mid] > nums[r]) {
                l = mid+1;
            } else {
                r = mid;
            }
        }
        
        int x = BinarySearch(nums, 0, l-1, target);
        x = x != -1 ? x : BinarySearch(nums, l, nums.size()-1 , target);
        return x;
    }
};

python3
先二分查找断点K,然后二分查找目标

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        L = len(nums)
        if L == 1 :
            if nums[0] == target:
                return 0
            else:
                 return -1
        if nums[0] == target:
            return 0
        if nums[-1] == target:
            return L - 1
        low = 0
        up = L - 1
        while low <= up:
            mid = (up + low)//2
            if mid == L-1 or nums[mid]>nums[mid+1]:
                k = mid
                break
            elif nums[mid] >= nums[0]:
                low = mid + 1
            else:
                up = mid - 1

        if target > nums[0]:
            up = k
            low = 0
        else:
            low = k+1
            up = L-1
        while low <= up:
            mid = (up + low) // 2
            if nums[mid] > target:
                up = mid -1 
            elif nums[mid] < target:
                low = mid + 1
            else:
                return mid
        return -1

嗯有道理,找断点也应该用二分法如同153题。代码修改入下

def bin_search(a, x, lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x: lo = mid + 1
        else: hi = mid
    return lo

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo+hi) // 2
            if nums[mid] > nums[-1]: lo = mid + 1
            else: hi = mid
        t = lo
        res = bin_search(nums, target, 0, t)
        if res == 0 and nums[0] != target: res = bin_search(nums, target, t, len(nums))
        if (res == t and nums[t] != target) or res == len(nums) or nums[res] != target:
            return -1
        return res

你这个的worst case(断点在数组末端的时候)的复杂度是O(n)啊,跟直接线性搜索target一样啊。