看到有序数组，无论数组里面是字符还是数字，都可以用二分查找解决。总体算法工作过程与线性扫描方法类似，除了找最左和最右下标的方法。这里我们仅仅做几个微小的调整，用这种修改过的二分查找方法去搜索这个排过序的数组。首先，为了找到最左边（或者最右边）包含 target 的下标（而不是找到的话就返回 true ），所以算法在我们找到一个 target 后不能马上停止。我们需要继续搜索，直到 lo == hi 且它们在某个 target 值处下标相同。将hi设置为len(nums)很巧妙，最后通过判断left_idx 和 len(nums)相比是否相等，就可以知道是不是有效最右下标，细节就是魔鬼。

题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。

示例

示例 1:

1 2	`输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]`

示例 2:

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

考察知识点

数组、二分查找

核心思想

二分查找+左右扩展

先用二分查找确定一个target的位置，然后向左向右拓展。

线性扫描

想法
对 target 检查每一个下标，一定能得到正确答案。

算法
首先，我们对 nums 数组从左到右做线性遍历，当遇到 target 时中止。如果我们没有中止过，那么 target 不存在，我们可以返回“错误代码” [-1, -1] 。如果我们找到了有效的左端点坐标，我们可以坐第二遍线性扫描，但这次从右往左进行。这一次，第一个遇到的 target 将是最右边的一个（因为最左边的一个存在，所以一定会有一个最右边的 target）。我们接下来只需要返回这两个坐标。

纯二分查找

强烈推荐该方法利用了减治思想设置巧妙且满足条件关于二分法的减治思想版本见35题

想法
因为数组已经排过序了，我们可以使用二分查找的方法去定位左右下标。

算法
总体算法工作过程与线性扫描方法类似，除了找最左和最右下标的方法。这里我们仅仅做几个微小的调整，用这种修改过的二分查找方法去搜索这个排过序的数组。首先，为了找到最左边（或者最右边）包含 target 的下标（而不是找到的话就返回 true ），所以算法在我们找到一个 target 后不能马上停止。我们需要继续搜索，直到 lo == hi 且它们在某个 target 值处下标相同。

另一个改变是 left 参数的引入，它是一个boolean类型的变量，指示我们在遇到 target == nums[mid] 时应该做什么。如果 left 为 true ，那么我们递归查询左区间，否则递归右区间。考虑如果我们在下标为 i 处遇到了 target ，最左边的 target 一定不会出现在下标大于 i 的位置，所以我们永远不需要考虑右子区间。当求最右下标时，道理同样适用。

代码步骤

1、声明extreme_insertion_index函数，再二分查找的基础上，引入left，当left为真的时候，寻找最左边界/最左下标。extreme_insertion_index是基于2分法，在寻找左边界、有边界。
1.1、声明lo和hi
1.2、开始while循环，如果 target = nums[mid]或者left != True ，那么我们递归查询左区间，因为由于原来的序列是升序的，那么左边界，肯定不会在右区间，要么在当前位置，要么在当前位置的左边，更新hi。否则，如果nums[mid] <= target 且 left != True，则去右区间找，更新lo
1.3、无论是找最左下标还是最右下标，返回的都是lo，因为while循环结束的条件是lo==li
2、开始searchRange
2.1、先找最左小标
2.2、特判left_idx是否找到，如果连left_idx都找不到，那就是不存在了。left_idx == len(nums)代表着，lo一直在增加，增加到了hi也没找着，而hi=len(nums)却一直没变化。另外一种情况是，hi被调低了，但是直到最后lo=hi时，nums[hi]实际上也不是target。
2.3、再找最右下标

这里，将hi设置为len(nums)很巧妙，最后通过判断left_idx 和 len(nums)相比是否相等，就可以知道是不是有效最右下标，细节就是魔鬼。

LeetCode题解

剑指offer思路

找到第一个k，二分查找算法总是先拿数组中间的数字和k作比较。
- 如果中间的数字比k大，那么k只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。
- 如果中间的数字比k小，那么k只有可能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。
- 如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k。
  - 如果中间数字的前面一个数字不是k，那么此时中间的数字刚好就是第一个k；
  - 如果中间数字的前面一个数字也是k，那么第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。
找到最后一个k，二分查找算法总是先拿数组中间的数字和k作比较。
- 如果中间数字比k大，那么k只能出现在数组的前半段。
- 如果中间数字比k小，那么k只能出现在数组的后半段。
- 如果中间数字等于k呢？我们需要判断这个k是不是最后一个k。
  - 如果下一个数字不是k，则中间数字就是最后一个k：
  - 如果下一个数字也是k，下一轮我们还是要在数组的后半段中去查找。
获得第一个k和最后一个k的位置，就能计算出k在数组中出现的次数了。

Python版本

二分查找+左右扩展

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

            # res = []
            if len(nums) == 0:
            return [-1, -1]

        if len(nums) == 1 and nums[0] == target:
            return [0, 0]

        first_find = search(0, len(nums)-1)
        if first_find == -1:
            return [-1, -1]
        else:  # 开始扩展
            right = first_find
            left = first_find
            while True:  # 从first_find位置向两边寻找
                stop_left_find = True
                stop_right_find = True
                if right + 1 < len(nums) and nums[right + 1] == target:  # 说明右边有效
                    right += 1
                    stop_left_find = False
                if left - 1 >= 0 and nums[left - 1] == target:  # 说明左边有效
                    left -= 1
                    stop_right_find = False
                
                if stop_left_find and stop_right_find :
                    break
            return [left, right]


print("leet code accept!!!")
Input = [[3, 3, 3], [1, 4], [2, 2], [], [5,7,7,8,8,10], [5,7,7,8,8,10]]
Input1 = [3, 4, 3, 0, 8, 6]
Answer = [[0, 2], [1, 1], [-1, -1], [-1, -1], [3, 4], [-1, -1]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.searchRange(Input[i], Input1[i])
        print(result==Answer[i])

时间复杂：最好的情况，只有一个target，只需要一次二分查找，不用拓展，时间复杂度为\(O(log_{2}N)\)，也可以表示为\(O(logN)\)。最坏情况，全部n个数都是target，这样一来，一次二分查找之后，还要进行n次扩展，才能得到正确的right和left，时间复杂度为\(O(log_{2}N + \frac{N}{2})\)
执行用时 :40 ms, 在所有 Python3 提交中击败了95.55%的用户
内存消耗 :14.4 MB, 在所有 Python3 提交中击败了25.96%的用户

线性扫描

class Solution:
    def searchRange(self, nums, target):
        # find the index of the leftmost appearance of `target`. if it does not
        # appear, return [-1, -1] early.
        for i in range(len(nums)):
            if nums[i] == target:
                left_idx = i
                break
        else:
            return [-1, -1]

        # find the index of the rightmost appearance of `target` (by reverse
        # iteration). it is guaranteed to appear.
        for j in range(len(nums)-1, -1, -1):
            if nums[j] == target:
                right_idx = j
                break

        return [left_idx, right_idx]

时间复杂度： \(O(n)\)。
这个暴力解法检测了num 数组中每个元素恰好两次，所以总运行时间是线性的。
空间复杂度： \(O(1)\) 。
线性扫描方法使用了固定大小的数组和几个整数，所以它的空间大小为常数级别的。

纯二分查找

class Solution2:
    # 声明extreme_insertion_index函数，再二分查找的基础上，引入left，当left为真的时候，寻找最左边界/最左下标。extreme_insertion_index是基于2分法，在寻找左边界、有边界。
    def extreme_insertion_index(self, nums, target, left):
        lo = 0  # 无论是找最左下标还是最右下标，返回的都是lo，因为while循环结束的条件是lo==li
        hi = len(nums)

        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (left and target == nums[mid]):  # 如果 target = nums[mid] 或者 left != True ，那么我们递归查询左区间，因为由于原来的序列是升序的，那么左边界，肯定不会在右区间，要么在当前位置，要么在当前位置的左边。
                hi = mid  # 因为是要去找最左下标，所以调低hi
            else:  # 如果nums[mid] <= target 且 left != True，则去右区间找
                lo = mid+1  # 

        return lo

    def searchRange(self, nums, target):
        # 先找最左小标
        left_idx = self.extreme_insertion_index(nums, target, True)

        # 特判left_idx是否找到，如果连left_idx都找不到，那就是不存在了。left_idx == len(nums)代表着，lo一直在增加，增加到了hi也没找着，而hi=len(nums)却一直没变化。另外一种情况是，hi被调低了，但是直到最后lo=hi时，nums[hi]实际上也不是target。
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]

        # 再找最右下标
        return [left_idx, self.extreme_insertion_index(nums, target, False)-1]

时间复杂度： \(O(\log_{2}n)\)
由于二分查找每次将搜索区间大约划分为两等分，所以至多有 \(\lceil \log_{2}n \rceil\)次迭代。二分查找的过程被调用了两次，所以总的时间复杂度是对数级别的。
空间复杂度：\(O(1)\) ，所有工作都是原地进行的，所以总的内存空间是常数级别的。
执行用时 :44 ms, 在所有 Python3 提交中击败了94.14%的用户
内存消耗 :14.3 MB, 在所有 Python3 提交中击败了26.04%的用户

剑指offer思路

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 注意特判
        if len(nums) == 0: return 0
        if len(nums) == 1:
            if nums[0] == target:
                return 1
            else:
                return 0
        index_first = self.getFirst(nums, target)
        index_last = self.getLast(nums, target)

        if index_first != -1 and index_last != -1:  # 由于index_first可能等于0，所以这里要设置index_first != -1 and index_last != -1，不能 index_first and index_last
            return index_last - index_first + 1 if index_first != index_last else 1 # 只有一个数字
        else:  # 不存在这个数字
            return 0


    def getFirst(self, nums, target):
        left = 0
        right = len(nums) - 0
        while left < right:
            middle = left + (right - left) // 2
            if nums[middle] == target:
                if middle == 0 or nums[middle-1] != target:  # 第一个
                    return middle
                else:  # 非最后一个，最后一个在前半段。
                    right = middle
            elif nums[middle] > target:  # 去前半段里面找
                right = middle
            else:  # 去后半段找
                left = middle + 1 
        return -1  # 找不到就返回 -1
   
    def getLast(self, nums, target):
        left = 0
        right = len(nums) - 0
        while left < right:
            middle = left + (right - left) // 2
            if nums[middle] == target:
                if middle == (len(nums)-1) or nums[middle+1] != target:  # 最后一个
                    return middle
                else:  # 非最后一个，最后一个在后半段。
                    left = middle + 1
            elif nums[middle] > target:  # 去前半段里面找
                right = middle
            else:  # 去后半段找
                left = middle + 1 
        return -1  # 找不到就返回 -1

注意特判
注意二分查找的默认返回值设置为 -1
注意 left = middle-1，right = middle 的情况下，循环条件是 left < right 。不能写成 left = middle-1，right = middle+1，循环条件为 left <= right。

LeetCode 剑指offer

二分查找和搜索

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LeetCode 35. 搜索插入位置（易）上一篇

LeetCode 33. 搜索旋转排序数组（中）下一篇

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置（中）& 剑指offer 面试题53 - I. 在排序数组中查找数字 I（易）

题目

示例

考察知识点

核心思想

二分查找+左右扩展

线性扫描

纯二分查找

剑指offer思路

Python版本

二分查找+左右扩展

线性扫描

纯二分查找

剑指offer思路