二分简介

• 适用条件：有序数组

• 原理：通过比较中间元素和目标值来逐步缩小搜索范围，每次将搜索范围减半，从而加快查找速度

• 时间复杂度：O(logn)

• 流程：
• 初始化左右指针：left 初始化为 0，right 初始化为 array.length - 1。
• 计算中间位置：避免 (left + right) / 2 可能导致的整数溢出，使用 left + (right - left) / 2。
• 比较和移动指针：
• 如果 mid 位置的元素是目标，根据不同要求做不同处理（看后文）
• 如果目标较大，移动左指针到 mid + 1。
• 如果目标较小，移动右指针到 mid - 1。
• 循环直至找到元素或指针重合：使用 while(left <= right) 保证在所有元素都被检查之前循环继续。

基本模版

查找指定数字的位置

查找指定数字第一次出现的位置

查找指定数字最后一次出现的位置

归纳

• 对于上面的三种应用场景，无论是查找数字位置、第一次出现的位置、最后一次出现的位置，都有下面的处理：
• nums[mid] < target：left = mid + 1
• nums[mid] > target：right = mid - 1;

• 不同点在于当nums[mid] == target时：
• 查找数字出现位置：直接返回
• 查找数字首次出现的位置：right = mid - 1（在左半区继续查找）
• 查找数字最后出现的位置：left = mid + 1（在右半区继续查找）

题目

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

34. 在排序数组中查找元素的第一个和最后一个位置 - 给你一个按照非递减顺序排列的整数数组 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]   提示： * 0 <= nums.length <= 105 * -109 <= nums[i] <= 109 * nums 是一个非递减数组 * -109 <= target <= 109

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/