算法模式：改进的二分查找
在上一篇文章 算法模式：前缀和 介绍了前缀和的算法模式。本篇文章，继续介绍数组相关的算法模式：改进的二分查找。
二分查找 二分查找相比每一个学过计算机算法的小伙伴都了解，时间复杂度是： \$\log_2N\$，是一个非常高效的数组查找算法。当然，前提是数组必须有序。过程如下：
图 1. 二分查找 LeetCode 704. 二分查找 就是一个标准的二分查找的算法题。代码如下：
/** * @author D瓜哥 · https://www.diguage.com * @since 2024-09-14 19:52:26 */ public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } 除了在排序数组中查找特定的值，二分查找还可以用于找边界和在旋转数组中查值。
找边界：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 LeetCode - 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 \$log_2n\$ 的算法解决此问题。
示例 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] 提示：