Dichotomy search

thinking

By maintaining the three indexes in the left, middle and right, we constantly lose half of the impossible search space, and continue to search in the other half until success

The basic dichotomous template is as follows:

    def search(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:  
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] <target:
                left = mid+1
            else:
                right = mid-1
        return -1

Using the basic dichotomous template, we can find the square root and guess the number

Search rotation sort array

The topic requires time complexity O(logn), so the binary search method is selected

Because the sorting array rotates, only one side can keep order after dividing two sides

If the left side is in order and the target value is in the left side range, it is normal dichotomy, otherwise, it is taken as the right side
If the right side is in order and the target value is in the right side range, the normal score is two points, otherwise, the left side is taken

def search(self, nums, target):
        left = 0
        right = len(nums)-1
        while left <= right:  
            mid = (left + right) // 2
            n = nums[mid]
            print(left,right,n)
            if n == target:
                return mid
            if n > nums[left]:
                if n > target and target >= nums[left]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif n < nums[right]:
                if n < target and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                left += 1
        return -1

First wrong version

The difference from the previous one is to find the dividing point between error and non error, so there is a side that can't skip mid and ensure that a left is the last correct version and a right is the first wrong version

def firstBadVersion(self, n):
        left = 0
        right = n
        while left < right:
            mid = (left+right)//2
            
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left 

Looking for peaks

You need to directly access the right element and select the left side to ensure that mid = right

class Solution:
    def findPeakElement(self, nums):
        if len(nums) == 0:
            return 0
        left = 0
        right = len(nums)-1
        while left<right:
            mid = (left+right)//2
            if nums[mid]>nums[mid+1]:
                right = mid
            else:
                left = mid + 1
        return left

Find the minimum value in the rotation sort array

The array value must be greater than the previous item. If the mid is less than the last item, the right ordered minimum value is on the left
If mid is greater than last, the minimum value is on the right

It can be further modified. Left and right are in order and return to left directly

      def findMin(self, nums):
        left = 0
        right = len(nums)-1
        while left<right:
            
            if nums[left]<nums[right]:
                return nums[left]
            
            mid = (left+right)//2
            n = nums[mid]
            if n<nums[mid-1]:
                return n
            elif n>=nums[left] :
                left = mid + 1
            else:
                right = mid 
                
        return nums[left]