基本知识

数组元素按照顺序排列
数组元素无法删除，只能替代（填充）
python 中，使用 list，代码中 List 是类型注解中的一种表示方式，通常出现在类型提示中。python 3.9 之后可以使用内置的 list 来替代 List。

704. 二分查找

题目链接 link

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

两个要点

数组中元素按照顺序排列
无重复的数字（否则元素下标不唯一）
- 如果有重复的数字，要求返回最小的那个呢？

解法

区间定义：定义 target 所在的区间是左闭右开还是左右全闭
核心：将数组分割为三个部分
- 左右全闭：[0, middle-1] , middle, [middle + 1, len - 1] 或者
- 左开右闭：[0, middle) , middle, [middle + 1, len)

左右全闭

区间为 [left, right]：
- 定义 right 为 len(nums) - 1，因为 right 要有含义
- 循环条件 while(left <= right) ，因为left == right是有意义的
- 判断条件，若 middle 大于 target ，则遍历左区间，设置 right = middle - 1，因为此时为右闭区间，不会再访问 middle；同理，若 middle 小于 target，则遍历右边区间，设置 left = middle + 1，同样因为是闭区间，不会再访问 middle。

代码：

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

左闭右开

区间为 [left, right)：
- 定义 right 为 len(nums)，因为不会访问 right，所以设置为区间长度
- 循环条件 while(left < right) ，因为left == right没有意义（右边为开区间）
- 判断条件，若 middle 大于 target ，则遍历左区间，设置 right = middle，因为此时为右开区间，设置 right=middle 实际上下一次会访问 middle - 1 。

代码：

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

相关题目1：35. 搜索插入位置

题目链接 link

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

要点

无重复元素 + 升序排列，考虑二分查找
这道题相较于二分查找，只是多了一个 target 不存在的情况，在这个情况下，一定满足 left == right + 1 （左右都为闭区间的情况）
- 因为，在循环的最后一轮，满足 left == right，此时只剩下最后一个数字，middle 也为 left （right）。此时若 middle 数小于 target，则 left + 1，反之则 right - 1。
- 基于这个原理，若 middle 数小于 target，target 应该放在 middle + 1 上，若 middle 数大于 target，则 target 应该放在 middle 上
- 对比上述两条，可以发现：
  - middle 数小于 target，left + 1，放在 middle + 1的位置
  - middle 数大于 target， right - 1, middle 不变，放在 middle 的位置
  - middle 的变化和 left 相同，即小于时加1，大于时不变，而最后一轮循环时 middle、left、right 均相同，则最后的结果一定为 left。

代码如下，只需将二分查找的代码的最后一行，改为 return left 即可

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

相关题目2：34. 在排序数组中查找元素的第一个和最后一个位置

题目链接 link
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

思路

相似于二分查找，分别找左边界和右边界，找到一个目标后

若要找左边界，则在找到的目标的左边数组中再次查找，right = middle - 1。即认为当前找到的数比实际的 target 大。

相似的，若要找右边界，则在找到的目标的右边数组中再次查找，left = middle + 1。即认为当前找到的数比实际的 target 小。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> int:
        
        leftb = mySearch(nums, target, True)
        rightb = mySearch(nums, target, False)

        def mySearch(nums: List[int], target: int, side: bool):
            left = 0
            right = len(nums) - 1
            res = -1

            while left <= right:
                middle = int((left + right) / 2)
                if nums[middle] > target:
                    right = middle - 1
                elif nums[middle] < target:
                    left = middle + 1
                else:
                    res = middle
                    if side:
                        # 左边界
                        right = middle - 1
                    else:
                        left = middle + 1
            return res


        return [leftb, rightb]