二分查找，又称折半查找，是一种常用的查找算法，可以在有序数组中快速查找指定元素。本文将从多个角度分析二分查找的实现。
1. 基本思路
二分查找的基本思路是将有序数组从中间分成两个部分，如果中间元素等于目标元素，查找成功返回该元素的索引；如果中间元素大于目标元素，则在左半部分继续查找；如果中间元素小于目标元素，则在右半部分继续查找。每次查找都将数组缩小一半，直到找到目标元素或者数组为空。
2. 实现方式
二分查找的实现方式有多种，以下是常见的几种实现方式。
（1）递归实现
递归实现是最简单的实现方式之一，代码如下：
```
public static int binarySearch(int[] nums, int target) {
return binarySearch(nums, target, 0, nums.length - 1);
}
public static int binarySearch(int[] nums, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
return binarySearch(nums, target, left, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, right);
}
}
```
（2）非递归实现
非递归实现使用循环来实现，代码如下：
```
public static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
```
（3）查找第一个等于目标元素的位置
如果数组中包含多个等于目标元素的元素，可以使用以下代码查找第一个等于目标元素的位置：
```
public static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (left < nums.length && nums[left] == target) {
return left;
} else {
return -1;
}
}
```
（4）查找最后一个等于目标元素的位置
如果数组中包含多个等于目标元素的元素，可以使用以下代码查找最后一个等于目标元素的位置：
```
public static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right >= 0 && nums[right] == target) {
return right;
} else {
return -1;
}
}
```
（5）查找第一个大于等于目标元素的位置
可以使用以下代码查找第一个大于等于目标元素的位置：
```
public static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (left < nums.length) {
return left;
} else {
return -1;
}
}
```
（6）查找最后一个小于等于目标元素的位置
可以使用以下代码查找最后一个小于等于目标元素的位置：
```
public static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right >= 0) {
return right;
} else {
return -1;
}
}
```
3. 讨论
（1）时间复杂度
二分查找的时间复杂度是 O(log n)，其中 n 为数组大小。因为每次查找都会将数组缩小一半，最多需要查找 log n 次。
（2）空间复杂度
二分查找的空间复杂度是 O(1)，因为只需要额外的常量空间存储 left、right 和 mid 这些变量。
（3）优化
对于一些特殊情况，可以对二分查找进行优化。比如：
- 如果数组中的数据重复性比较高，可以通过二分查找加上遍历查找的方式来提高效率；
- 对于查找范围比较小的情况，可以使用顺序查找或者简单遍历来代替二分查找；
- 对于有序数组插入要求高的情况，可以使用插入排序、归并排序等算法进行预处理。
4.
微信扫一扫，领取最新备考资料
湖南希赛网络科技有限公司 版权所有 ©2001-2026 湘ICP备10203241号-14 湘公网安备43019002000749号
违法和不良信息举报 举报电话：18974879411 举报邮箱：wujunping@educity.cn
