二分查找

二分查找

二分查找是一种在有序数组中定位目标值的算法。通过维护左、右边界 L、R，取中间索引 M = (L+R)/2（或使用无符号右移避免溢出），比较 A[M] 与目标 T：相等则返回索引；小于 T 时左边界设为 M+1；大于 T 时右边界设为 M-1，循环直至 L>R 表示未找到。示例代码先对数组排序，再在 while 循环中实现上述逻辑，返回找到的下标或 -1。文中指出当 R 接近 Integer.MAX_VALUE 时 (L+R)/2 可能溢出，提供两种改进：使用 L/2+R/2 的等价写法或位运算 M = (L+R) >>> 1，以确保安全且提升效率。