二分搜索
提示
- 二分查找特点:二分查找是一种高效的查找算法,用于在已排序数组中查找特定元素,通过将搜索区间分为两半来减少搜索时间。
- 实现方法:二分查找可以通过迭代或递归方法实现,其中迭代方法直到两个指针相遇,而递归方法遵循分而 治之的策略。
- 应用场景:二分查找广泛应用于各种编程语言的库中,以及在调试过程中精确定位错误发生的位置。
二分查找是一种在已排序数组中查找元素位置的搜索算法。
在这种方法中,元素总是在数组的一部分中间位置被搜索。
二分查找只能在已排序的元素列表上实现。如果元素尚未排序,我们首先需要对它们进行排序。
二分查找的工作原理
二分查找算法可以通过以下两种方式实现,具体如下所述。
- 迭代方法
- 递归方法
递归方法遵循分而治之的方法。
下面讨论了这两种方法的通用步骤。
-
要进行搜索的数组是:
假设要搜索的元素
x = 4
。 -
分别在最低和最高位置设置两个指针 low 和 high。
-
找到数组的中间元素
mid
,即arr[(low + high)/2] = 6
。 -
如果 x == mid,则返回 mid。否则,将要搜索的元素与 m 比较。
-
如果
x > mid
,将x
与mid
右侧元素的中间元素比较。通过设置low = mid + 1
来完成。 -
否则,将
x
与mid
左侧元素的中间元素比较。通过设置high = mid - 1
来完成。 -
重复步骤 3 到 6,直到 low 与 high 相遇。
-
找到了
x = 4
。
二分查找算法
迭代方法
直到指针 low 和 high 相遇为止。
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x 在右侧
low = mid + 1
else // x 在左侧
high = mid - 1
递归方法
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x 在右侧
return binarySearch(arr, x, mid + 1, high)
else // x 在左侧
return binarySearch(arr, x, low, mid - 1)
Python、Java、C/C++ 示例(迭代方法)
# Python 中的二分查找
def binarySearch(array, x, low, high):
# 重复直到指针 low 和 high 相遇
while low <= high:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print("元素在索引 " + str(result) + " 处找到")
else:
print("未找到")
// Java 中的二分查找
class BinarySearch {
int binarySearch(int array[], int x, int low, int high) {
// 重复操作直到 low 和 high 指针相遇
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int array[] = { 3, 4, 5, 6, 7, 8, 9 };
int n = array.length;
int x = 4;
int result = ob.binarySearch(array, x, 0, n - 1);
if (result == -1)
System.out.println("未找到");
else
System.out.println("元素位于索引 " + result);
}
}
// C 中的二分查找
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
// 重复操作直到 low 和 high 指针相遇
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("未找到");
else
printf("元素位于索引 %d", result);
return 0;
}
// C++ 中的二分查找
#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high) {
// 重复操作直到 low 和 high 指针相遇
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int x = 4;
int n = sizeof(array) / sizeof(array[0]);
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("未找到");
else
printf("元素位于索引 %d", result);
}
Python、Java、C/C++ 示例(递归方法)
# Python 中的二分查找
def binarySearch(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
# 如果在中间找到,则返回它
if array[mid] == x:
return mid
# 搜索左半边
elif array[mid] > x:
return binarySearch(array, x, low, mid-1)
# 搜索右半边
else:
return binarySearch(array, x, mid + 1, high)
else:
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print("元素位于索引 " + str(result))
else:
print("未找到")
// Java 中的二分查找
class BinarySearch {
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// 如果在中间找到,则返回它
if (array[mid] == x)
return mid;
// 搜索左半边
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// 搜索右 半边
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int array[] = { 3, 4, 5, 6, 7, 8, 9 };
int n = array.length;
int x = 4;
int result = ob.binarySearch(array, x, 0, n - 1);
if (result == -1)
System.out.println("未找到");
else
System.out.println("元素位于索引 " + result);
}
}
// C 中的二分查找
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// 如果在中间找到,则返回它
if (array[mid] == x)
return mid;
// 搜索左半边
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// 搜索右半边
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("未找到");
else
printf("元素位于索引 %d", result);
}
// C++ 中的二分查找
#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// 如果在中间找到,返回其位置
if (array[mid] == x)
return mid;
// 搜索左半边
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// 搜索右半边
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int x = 4;
int n = sizeof(array) / sizeof(array[0]);
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("未找到");
else
printf("元素位于索引 %d", result);
}
二分查找的复杂度
时间复杂度
- 最优情况复杂度:
O(1)
- 平均情况复杂度:
O(log n)
- 最坏情况复杂度:
O(log n)
空间复杂度
二分查找的空间复杂度为 O(1)
。
二分查找的应用
- 在 Java、.Net、C++ STL 的库中
- 在调试时,二分查找用于精确定位错误发生的位置。