二分查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。二分查找的思想类似于分治思想。
一、基本思想
实现二分法排序，首先要明确基本思想，即：在有序数组中，每次取数组的中间位置，如果该位置上的值不是要查找的值，继续在大于或者小于它的那一半中查找，直到查找到目标为止。
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没有找到
}
二、时间复杂度
二分法排序的时间复杂度为 O(log n)。因为每次都会将数组缩小一半，在最坏的情况下，需要进行 log n 次操作才能找到目标元素。
三、适用条件
二分法排序仅适用于有序数组。在无序数组中查找元素，需要先将数组排序再进行查找。
四、如何处理重复元素
有时候数组中可能会有重复的元素，怎么办呢？
一种方法是，在查找到目标元素的时候，向前或向后遍历，查找其他相同的元素。这种方法的时间复杂度为 O(k)，其中 k 为相同元素的个数，因此效率较低。
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left = 0 && arr[i] == target) { i--; }
int j = mid + 1;
while (j < arr.length && arr[j] == target) { j++; }
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没有找到
}
另一种方法是，在进行比较的时候，判断中间值是否包含在目标区间内。
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
if (mid == 0 || arr[mid - 1] < target) {
return mid;
} else {
right = mid - 1;
}
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没有找到
}
五、应用场景
二分法排序最常用的应用场景是在数组中查找元素。除此之外，二分法排序还可以用于一些其他的问题，例如求开方、最大值（最小值）等。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/193727.html
微信扫一扫 
支付宝扫一扫 