0.11 二分查找

[35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left
```

[74. 搜索二维矩阵](https://leetcode.cn/problems/search-a-2d-matrix/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        r_left, r_right = 0, m - 1
        while r_left <= r_right:
            r_mid = (r_left + r_right) // 2
            if matrix[r_mid][0] < target:
                r_left = r_mid + 1
            elif matrix[r_mid][0] > target:
                r_right = r_mid - 1
            else:
                return True
        c_left, c_right = 0, n - 1
        while c_left <= c_right:
            c_mid = (c_left + c_right) // 2
            if matrix[r_left - 1][c_mid] < target:
                c_left = c_mid + 1
            elif matrix[r_left - 1][c_mid] > target:
                c_right = c_mid - 1
            else:
                return True
        return False
```
[34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def searchStart(self, nums, target):
        n = len(nums)
        left, right = 0, n-1
        while left <= right:
            mid = (left + right)//2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left
        
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.searchStart(nums, target)
        end = self.searchStart(nums, target+1)
        return [-1,-1] if start == len(nums) or nums[start] != target else [start, end-1]
```
[33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
        return -1
```
[153. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid - 1
        return nums[left]
```
[4. 寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = nums1 + nums2
        nums.sort()
        n = len(nums)
        mid = n // 2
        if n % 2 == 0:
            return (nums[mid] + nums[mid-1])/ 2
        else:
            return nums[mid]
```
```
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        i = j = 0
        nums = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                nums.append(nums1[i])
                i += 1
            else:
                nums.append(nums2[j])
                j += 1
        nums.extend(nums1[i:])
        nums.extend(nums2[j:])
        n = len(nums)
        mid = n // 2
        if n % 2 != 0:
            return float(nums[mid])
        else:
            return (nums[mid-1] + nums[mid])/2
```