二分查找算法（Binary Search Algorithm）也叫折半查找是一种在有序数组中查找特定元素的搜索算法。其基本思想是通过不断将搜索区域减半来快速定位目标值，每次比较中间元素与目标值的大小关系，从而决定是在左半部分还是右半部分继续查找。
以下是二分查找算法的一般步骤：
首先，确定待查找的有序数组，并获取其最大下标（或长度）。
计算数组的中间索引：mid = low + (high - low) / 2，其中low为当前查找区间的起始索引，high为结束索引。
检查中间位置的元素是否是要查找的目标值，若是，则查找结束，返回该索引；若不是，则根据目标值与中间元素的关系调整查找区间：
如果目标值小于中间元素，那么在数组的左半部分（即从low到mid-1）继续进行二分查找，即将high更新为mid-1；
如果目标值大于中间元素，那么在数组的右半部分（即从mid+1到high）继续进行二分查找，即将low更新为mid+1；
重复步骤2和3，直到找到目标值或者low大于high（表示未找到目标值，此时通常返回-1或其他特殊值表示未找到）。
二分查找的时间复杂度为O(log n)，空间复杂度为O(1)，适用于大规模且有序的数据集合。
假设我们有一个有序数组 arr = [1, 3, 5, 6, 8, 9, 10]，我们要在这个数组中查找数字7。
初始时，我们将整个数组看作查找区间，low=0，high=6（因为数组下标是从0开始的，所以最后一个元素的下标是6）。
第一步： 计算中间索引 mid = (0 + 6) / 2 = 3，得到中间元素arr[3]=6，但6不等于我们的目标值7。
第二步： 因为7 > 6，所以我们知道目标值7肯定在数组的右半部分（即从索引4到6的部分），因此我们将low更新为mid+1=4，high保持不变，此时查找区间变为[4, 6]。
第三步： 重新计算新的中间索引 mid = (4 + 6) / 2 = 5，得到中间元素arr[5]=9，但9仍然不等于7。
第四步： 因为7 < 9，目标值7应该在数组的左半部分（即从索引4到4的部分），但由于此时左边界和右边界相邻，我们已经确定数组中没有7，因此结束查找，返回未找到结果。
总结：在实际应用中，如果数组中存在目标值，二分查找会在log(n)的时间复杂度内找到它。在上述示例中，虽然7不在数组中，但通过四次比较（log_2(7)≈3），我们也确定了这一点。
下面是一段使用非递归方式实现的Java二分查找算法代码：
public class BinarySearch {
// 非递归实现二分查找
public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 计算中间索引，避免整数溢出可改为 (left + right) >>> 1
if (nums[mid] == target) { // 找到了目标值
return mid;
} else if (nums[mid] < target) { // 目标值在右半部分
left = mid + 1;
} else { // 目标值在左半部分
right = mid - 1;
}
}
// 没有找到目标值
return -1;
}
public static void main(String[] args) {
int[] sortedArray = {1, 3, 5, 6, 8, 9, 10};
int targetValue = 7;
int result = binarySearch(sortedArray, targetValue);
if (result != -1) {
System.out.println("找到了目标值 " + targetValue + "，它在数组中的索引是: " + result);
} else {
System.out.println("未在数组中找到目标值 " + targetValue);
}
}
}这段代码首先定义了一个名为binarySearch的方法，接受一个已排序的整数数组nums和一个目标值target作为参数。在方法内部，通过while循环持续更新查找区间，直至找到目标值或左右边界交叉（left > right）。当找到目标值时返回对应的索引，否则返回-1表示未找到。在main方法中展示了如何调用该二分查找方法并处理结果。
原文链接: https://www.yukx.com/arithmetic/article/details/2468.html 优科学习网二分查找算法
