二分查找是在已排序数组中快速定位目标值的算法，时间复杂度o(log n)；核心前提是数组必须升序或降序排列，无序时需先排序但通常不划算。
什么是二分查找？核心前提是什么？
二分查找是一种在已排序数组中快速定位目标值的算法，时间复杂度为 O(log n)，远优于线性查找的 O(n)。它的核心前提是：数组必须是升序（或降序）排列的；如果无序，必须先排序（但排序本身会带来额外开销，通常不划算）。
php 中如何手写一个健壮的二分查找？
面试时考的不是调用函数，而是手动实现逻辑。关键点包括：边界控制、避免整数溢出、循环/递归选择、返回值含义（下标 or -1）。以下是推荐的迭代写法（更安全、不易栈溢出）：
// 升序数组中查找目标值，返回索引，未找到返回 -1
function binarySearch(Array $arr, int $target): int {
$left = 0;
$right = count($arr) – 1;
while ($left
$mid = $left + (int)(($right – $left) / 2); // 防止 $left+$right 溢出
if ($arr[$mid] === $target) {
return $mid;
} elseif ($arr[$mid]
$left = $mid + 1;
} else {
$right = $mid – 1;
}
}
return -1;
}
面试常问的变种题怎么应对？
- 查找第一个/最后一个等于目标值的位置：不匹配时不能直接 return -1，需继续收缩边界。例如找首次出现位置，当 $arr[$mid] == $target 时，不返回，而是 $right = $mid – 1，并用变量记录答案。
- 查找插入位置（如 LeetCode 35）：循环结束时 $left 就是目标应插入的下标（保持有序），无需额外判断。
- 旋转排序数组中查找（如 [4,5,6,7,0,1,2]）：先判断哪半边有序，再根据 target 落在有序侧还是无序侧决定搜索方向。
- 二维数组中查找（m×n 矩阵，每行升序，每列升序）：可从右上角或左下角开始，利用单调性每次排除一行或一列，O(m+n) 解决，而非强行套二分。
容易踩坑的细节有哪些？
- 循环条件写成
$left 会导致漏判单元素情况，正确是 <code>$left 。 - 计算 $mid 用
($left + $right) / 2在大数时可能整型溢出（PHP 8+ int 更大，但习惯要养好），推荐$left + (int)(($right - $left) / 2)。 - 边界更新写成
$left = $mid或$right = $mid容易死循环，必须跳过已检查的 $mid，即+1或-1。 - 比较时用
===而非==，避免类型隐式转换导致误判（比如查找字符串 ‘0’ 时遇到数字 0）。