Day2——二分查找

打卡题目：leetcode第35题，搜索插入位置
类似题目：278、704
注：通过刷题，一定要掌握二分查找变形题的基本公式。比如，查找第一个等于target的、查找第一个小于target的、查找最后一个等于target的……
二分查找暂时分为两次刷题：

• 一是掌握二分查找公式及常用变形解决思路
• 二是掌握旋转数组的二分查找

【思路】

1. 暴力解法：遍历数组，查找元素。
2. 二分查找：题目类型为找到第一个大于等于target的元素，返回其位置。

【代码】

# 二分查找通用模板
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] >= target:
                r = mid - 1
            else:
                l = mid + 1
        return l