Leetcode 刷题笔记 (binary search)

二分法

34. Find First and Last Position of Element in Sorted Array（medium)69. Sqrt(x) （easy)

l = 0, r = 0, mid = (l + r) // 2二分法就是首尾双指针 （每轮移位为一个区间）nums[mid] > target >>> r = mid - 1；else： l = mid + 1时间复杂度 O（logn)

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = 0
        r = len(nums) - 1
        res = -1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                res = mid
                break
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        if res == -1:
            return [-1, -1]
        #step 1 [l, res]--> 有几个res即[1,...,res,res,res]
        l = 0
        r = res
        l_bound = 0
        r_bound = 0
        while l <= r:
            mid = (l+r)//2
            if nums[mid] == target:
                r = mid - 1
                l_bound = mid
            else: 
                l = mid + 1
        l = res
        r = len(nums) - 1
        while l <= r: 
            mid = (l + r) // 2
            if nums[mid] == target:
                r_bound = mid
                l = mid + 1
            else:
                r = mid - 1
        return [l_bound, r_bound]

三轮二分，

第一轮确认一个target的位置作为mid第二轮确认[l , mid] 中间是否还有target第三轮[mid , r] 中间是否有target

https://leetcode.com/problems/sqrtx/

class Solution:
    def mySqrt(self, x: int) -> int:
        l = 0
        r = x
        while l <= r:
            mid = (l + r) // 2
            if mid * mid == x:
                return mid
            elif mid * mid > x:
                r = mid - 1
            else:
                l = mid + 1
        return r
        

因为题目取下界故 return r，
因为while循环的推出时[r , l] >>> 为所取平方根的区间