二分查找解读（基于Java实现）
原创
二分查找也叫折半查找，是一种在已排好序的数组中查找某一特定元素的搜索算法。其基本思想是将要查找的区间的中间位置与目标值进行比较，根据比较结果来确定下一步要查找的区间，从而逐步缩小查找范围，直到找到目标值或者确定目标值不存在为止。
二分查找的实现过程如下：
- 取得数组的中间位置 mid。
- 将目标值与中间位置的元素进行比较，如果相等，则直接返回 mid。
- 如果目标值比中间位置的元素小，则在左半部分继续查找；如果目标值比中间位置的元素大，则在右半部分继续查找。
- 重复执行步骤 1 到步骤 3，直到找到目标值或者确定目标值不存在。
二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。由于每次查找都可以将查找范围减半，因此该算法的时间复杂度是非常优秀的。
假设数组的长度为 n，则在最坏情况下，如果要查找的元素不在数组中，那么最多需要执行 log2(n) 次查找操作才能确定该元素不存在。这是因为每次查找可以将查找范围缩小一半，所以经过 log2(n) 次查找后，查找区间最多缩小到一个元素。因此，二分查找的时间复杂度为 O(log n)。
二分查找的空间复杂度为 O(1)，因为它只需要使用常数级别的额外空间来存储指针、变量等临时数据。因此，二分查找的空间复杂度是非常小的，不需要额外的空间开销。
伪代码：
Function binarySearch(arr, n, target):
left = 0
right = n - 1
while left <= right:
mid = (left + right) / 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
接收一个已排序的数组 arr，数组长度为 n，以及目标值 target。函数使用两个指针 left 和 right 分别指向数组的左右两端，并在一个 while 循环中进行查找。每次循环中，计算出当前区间的中间位置 mid，并将其与目标值进行比较。如果相等，则直接返回 mid；如果目标值比中间位置的元素小，则在左半部分继续查找；如果目标值比中间位置的元素大，则在右半部分继续查找。最后，如果没有找到目标值，则返回 -1。
力扣链接：https://leetcode.cn/problems/binary-search/
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4 示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 提示：
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。
基于java实现
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.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;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int target = 7;
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index " + result);
}
}
}
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。