二分查找
nothing-sy2023-11-14算法 搜索算法
TIP
二分查找 binary search」是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮减少一半搜索范围，直至找到目标元素或搜索区间为空为止。
思路
前提： 一个有序且不重复的数组
- 确定搜索区间，即确定搜索范围，即确定
left和right的值 - 确定搜索区间的中点，即确定
mid的值 (mid的索引一般为Math.floor((left + right)/2)，即向下取整的坐标，但是如果数组数据量很大，索引超过了integer的长度可能会导致溢出，所以用Math.floor(left + (right - left) / 2)去获取中间的索引更安全 - 比较
mid和target的大小，确定下一步的搜索区间 - 重复上述步骤，直到找到目标元素或搜索区间为空
以下是codeGeex AI提供的代码
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; //由于是双闭区间，因此left应该在mid基础上+1 ，否则会出现一直满足left<=right的条件进入死循环
} else {
right = mid - 1;//由于是双闭区间，因此right应该在mid基础上-1
}
}
return -1;
}