搜索算法：二分查找
二分查找（Binary Search）是一种高效的搜索算法，适用于已排序的数组或列表。通过每次将搜索范围减半，其时间复杂度为O(log n)，远优于线性查找的O(n)。
快速理解
二分查找（也叫折半查找）的思路特别像我们玩 “猜数字” 游戏：
- 比如猜 1~100 之间的数字，你先猜 50，对方说 “大了”，那你就知道答案在 1~49 之间；
- 再猜 25，对方说 “小了”，就知道答案在 26~49 之间；
- 每次都把查找范围缩小一半，直到找到目标值，或确定目标值不存在。
因此只要你的数据是有序的，二分查找就是最高效的选择。
算法核心思想
- 确定搜索范围：初始化左边界
left为 0，右边界right为数组长度减 1。 - 计算中间索引：取中间位置
mid = left + (right - left) // 2（避免整数溢出）。 - 比较目标值：
- 若
arr[mid] == target，返回mid。 - 若
arr[mid] < target，缩小范围至右半部分（left = mid + 1）。 - 若
arr[mid] > target，缩小范围至左半部分（right = mid - 1）。
- 若
- 终止条件（left <= right）：当
left > right时，说明目标不存在，返回-1.
代码实现(基础版java）
class Solution { // 准备一个无序数组，先排序（二分查找必须用有序数组！） public int search(int[] nums, int target) { // 1. 初始化左右边界 int left = 0,right = nums.length - 1; // 2. 循环查找 while(left<=right){ // 计算中间索引，避免溢出 int mid = (right + left)/2 ; int num = nums[mid]; if(num == target) { // 找到目标，返回索引 return mid; }else if(target > num){ // 目标在右半区，左边界右移 left = mid + 1; }else { // 目标在左半区，右边界左移 right = mid - 1; } } // 没找到返回-1 return -1; } }提醒（tips）：
必须先排序！二分查找的前提是数组有序。如果数组是乱的，比如
[5,2,9]，直接用二分查找会得到错误结果。一定要先用Arrays.sort()把数组排好序。mid 的计算方式不要写成
mid = (left + right) / 2，当left和right都是很大的数时，会导致整数溢出。正确写法是mid = left + (right - left) / 2。边界更新要加 1 / 减 1不要写成
left = mid或right = mid，这会导致死循环。因为如果arr[mid]不是目标值，这个位置就可以排除，所以要直接跳到mid + 1或mid - 1。循环条件是
left <= right如果写成left < right，会漏掉最后一个可能的元素。比如当left和right相等时，mid就是这个元素，不判断就会错过
总结（基础版）
应对大多数情况下一下步骤完全可以直接套用：
- 初始化边界：左指针
left=0，右指针right=数组长度-1； - 循环查找：当
left <= right时（有查找空间），计算中间索引mid = left + (right-left)/2（避免整数溢出，替代(left+right)/2）； - 比较缩范围：
arr[mid] == target：找到目标，返回mid；arr[mid] < target：目标在右半区，left = mid + 1；arr[mid] > target：目标在左半区，right = mid - 1；
- 未找到：循环结束无返回，返回
-1表示目标不存在。