上查看所有课程
二分查找是一种在已排序数组中查找元素位置的查找算法。
在这种方法中，元素始终在数组某个部分的中间进行搜索。
二分查找只能在已排序的项目列表中实现。如果元素尚未排序，则需要先对其进行排序。
二分查找工作原理
二分查找算法可以通过两种方式实现，如下所述。
- 迭代法
- 递归法
递归方法遵循分治法。
以下将讨论两种方法的一般步骤。
- 需要进行查找的数组是
初始数组
设x = 4为要查找的元素。 - 分别将两个指针 low 和 high 设置在最低和最高位置。
设置指针 - 求出数组的中间位置 mid，即
mid = (low + high)/2和arr[mid] = 6。
中间元素 - 如果
x == arr[mid]，则返回mid。否则，将要查找的元素与arr[mid]进行比较。 - 如果
x > arr[mid]，则将 x 与 arr[mid] 右侧元素的中点进行比较。这是通过将 low 设置为low = mid + 1来完成的。 - 否则，将 x 与 arr[mid] 左侧元素的中点进行比较。这是通过将 high 设置为
high = mid - 1来完成的。
查找中间元素 - 重复步骤 3 到 6，直到
low与high相遇。
中间元素 - 已找到
x = 4。
已找到
二分查找算法
迭代方法
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
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 is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the left side
return binarySearch(arr, x, low, mid - 1)
Python、Java、C/C++ 示例（迭代法）
二分查找可视化：不要仅仅阅读二分查找，亲眼看看它是如何工作的。使用我们新的 DSA 可视化工具，逐步查看算法的每一行是如何工作的。 亲自尝试！
# Binary Search in python
def binarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each other
while low <= high:
mid = low + (high - low)//2
if x == array[mid]:
return mid
elif x > array[mid]:
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("Element is present at index " + str(result))
else:
print("Not found")// Binary Search in Java
class BinarySearch {
int binarySearch(int array[], int x, int low, int high) {
// Repeat until the pointers low and high meet each other
while (low <= high) {
int mid = low + (high - low) / 2;
if (x == array[mid])
return mid;
if (x > array[mid])
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("Not found");
else
System.out.println("Element found at index " + result);
}
}// Binary Search in C
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
// Repeat until the pointers low and high meet each other
while (low <= high) {
int mid = low + (high - low) / 2;
if (x == array[mid])
return mid;
if (x > array[mid])
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("Not found");
else
printf("Element is found at index %d", result);
return 0;
}// Binary Search in C++
#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high) {
// Repeat until the pointers low and high meet each other
while (low <= high) {
int mid = low + (high - low) / 2;
if (x == array[mid])
return mid;
if (x > array[mid])
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("Not found");
else
printf("Element is found at index %d", result);
}Python、Java、C/C++ 示例（递归法）
# Binary Search in python
def binarySearch(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
# If found at mid, then return it
if x == array[mid]:
return mid
# Search the right half
elif x > array[mid]:
return binarySearch(array, x, mid + 1, high)
# Search the left half
else:
return binarySearch(array, x, low, mid - 1)
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("Element is present at index " + str(result))
else:
print("Not found")// Binary Search in Java
class BinarySearch {
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (x == array[mid])
return mid;
// Search the right half
if (x > array[mid])
return binarySearch(array, x, mid + 1, high);
// Search the left half
return binarySearch(array, x, low, 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("Not found");
else
System.out.println("Element found at index " + result);
}
}// Binary Search in C
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (x == array[mid])
return mid;
// Search the right half
if (x > array[mid])
return binarySearch(array, x, mid + 1, high);
// Search the left half
return binarySearch(array, x, low, 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("Not found");
else
printf("Element is found at index %d", result);
}// Binary Search in 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 found at mid, then return it
if (x == array[mid])
return mid;
// Search the right half
if (x > array[mid])
return binarySearch(array, x, mid + 1, high);
// Search the right half
return binarySearch(array, x, low, 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("Not found");
else
printf("Element is found at index %d", result);
}二分查找复杂度
时间复杂度
- 最佳情况复杂度：
O(1) - 平均情况复杂度：
O(log n) - 最坏情况复杂度：
O(log n)
空间复杂度
二分查找的空间复杂度为 O(1)。
二分查找应用
- 在 Java、.Net、C++ STL 的库中
- 在调试时，二分查找用于精确定位错误发生的位置。