二分查找也是经常考察的一道题目，很容易因为边界问题出错

搜索插入位置

常规的解法，增加不满足条件下的返回情况

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1 
        while start <= end:
            mid = int((start+end)/2)
            if nums[mid] == target:
                return mid
            elif nums[mid]>target:
                end = mid-1
                if end < start:
                    return mid
            else:
                start = mid + 1
                if start > end:
                    return mid+1

在题解中找到一种方法，如下：

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

标准的二分查找方法，left左边一直保持小于target的，right及其右边一直保持大于等于target，当left和right相等时仍成立，此时跳出循环，如果left/right 对应的值等于target，或者大于target，均返回left/right，且不可能小于target

搜索二维矩阵

二分查找：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in range(len(matrix)):
            left = 0
            right = len(matrix[i])-1
            while left <= right:
                mid = int((left+right)/2)
                if matrix[i][mid] == target:
                    return True
                elif matrix[i][mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

寻找峰值

二分查找做的话，常规利用 left/right/mid 这几个值来判断选哪一半，发现没法判断选哪一半，依照题目的提示，峰值即 当前值后前一个/后一个比较，因此想到用mid对应的值和mid+1对应的值比较，如果$num[mid] > num[mid+1]$，则左边一定有峰值，否则，峰值在右边

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

搜索旋转排序数组

二分查找的一大用处是作用在有序的数组，题目中给定的数组分成两半后，一定能找到一半是有序的，如果target在这一半中（[left,mid]），那利用常规有序数组的二分查找解决即可，不在则在另外一半中([mid+1,right])，注意边界：

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

在排序数组中查找元素的第一个和最后一个位置

常规解法，不同的是当满足条件时还需要判断左右边界，而判断左右边界又是一个二分查找，python实现如下：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = int((left + right)/2)
            if nums[mid] > target:
                right = mid -1
            elif nums[mid] < target:
                left = mid + 1
            else:
                r = mid - 1
                while left <= r:
                    m = int((left + r)/2)
                    if nums[m] != target:
                        left = m + 1
                    else:
                        r = m - 1
                l = mid + 1
                while l <= right:
                    m = int((l + right)/2)
                    if nums[m] != target:
                        right = m -1
                    else:
                        l = m + 1
                return r+1,l-1
        return -1,-1

寻找旋转排序数组中的最小值

同样是二分的思路，最小值要么在数组的第一个位置（原始序），要么在其他位置（发生了旋转），如果数组中最左边的元素小于最右边的元素，那么最小值一定在最左边，否则最小值在中间（其它位置），利用这一点不断的二分，直到找到一个数组，满足最左边的元素小于最右边的元素为止，注意边界：

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