什么是二分查找？
二分查找，也称折半查找，是一种常见的查找算法。它的基本思想是：将有序数组分成左右两部分，每次取中间位置的元素与目标值进行比较，如果中间位置元素等于目标值，则查找成功；否则根据中间元素与目标值的大小关系，可确定下一步查找的区间是左半部分还是右半部分。重复上述步骤，直到查找到目标值，或者确定目标值不存在。
二分查找的实现方式
迭代实现
迭代实现的二分查找代码如下：
int binary_search_iterative(int arr[], int target, int length)
{
int left = 0;
int right = length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
迭代方式的二分查找主要通过循环实现，每次循环可以将查找范围缩小一半，直到找到目标元素。
递归实现
递归实现的二分查找代码如下：
int binary_search_recursive(int arr[], int target, int left, int right)
{
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
return binary_search_recursive(arr, target, mid + 1, right);
else
return binary_search_recursive(arr, target, left, mid - 1);
}
递归方式的二分查找主要通过递归实现，在每一次递归中将查找范围缩小一半，直到找到目标元素。
二分查找的时间复杂度分析
二分查找的时间复杂度为O(log n)。
时间复杂度的分析：每一次比较后，查找范围会缩小一半，因此最多需要log n次比较。
二分查找的优化
二分法算法模板
1、模板一，查找某个数target：
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] < target) {
left = mid + 1;
} else if(nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
2、模板二，查找第一个大于等于某个数target的位置：
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] < target) {
left = mid + 1;
} else if(nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
right = mid - 1;
}
}
// 注意越界
if(left >= nums.length || nums[left] != target)
return -1;
return left;
}
3、模板三，查找最后一个小于等于某个数target的位置：
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] < target) {
left = mid + 1;
} else if(nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
left = mid + 1;
}
}
// 注意越界
if(right < 0 || nums[right] != target)
return -1;
return right;
}
以上三个模板可以在各种场景下进行优化，适应各种不同的数据处理需求。
二分查找的应用场景
二分查找主要适用于有序数组中的查找操作，可以用于处理多种数据处理需求。
1、查找某个元素是否出现在有序数组中；
2、查找某个元素在有序数组中的第一个位置；
3、查找某个元素在有序数组中的最后一个位置；
4、查找有序数组中比某个元素大的最小元素；
5、查找有序数组中比某个元素小的最大元素；
6、查找有序数组中与某个元素最接近的元素。
二分查找的应用场景广泛，可以优化数据处理效率。
总结
二分查找是一种常用的查找算法，可以在有序数组中快速查找元素的位置，时间复杂度为O(log n)。二分查找的实现方式有迭代和递归两种方式，递归方式代码简洁，可读性好，但容易栈溢出；迭代方式代码正常，性能较好。在实际使用过程中，可以根据数据处理需求使用不同的二分查找模板，适应各种场景下的需求。