二分查找

发表于 更新于 分类于 ， 阅读次数： 本文字数： 225 阅读时长 ≈ 1 分钟

二分查找也称 折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找

前提条件

数组有序

时间复杂度

二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用 \(O(logn)\) 时间完成搜索任务

基本思想

将 n 个元素分成个数大致相同的两半，取 a[n/2] 与 x 进行比较。

如果x=a[n/2]，则找到 x，算法终止。

如果 x<a[n/2], 则只要在数组 a 的左半部继续搜索 x。

如果 x>a[n/2]，则只要在数组 a 的右半部继续搜索 x。

Java 实现

  • 非递归
1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) return -1;

    int left = 0, 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;
}
  • 递归
1
2
3
4
5
6
7
8
9
10
11
public static int binarySearch2(int[] arr, int target, int left, int right) {
    if (arr == null || arr.length == 0) return -1;

    if (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) return binarySearch2(arr, target, mid + 1, right);
        else return binarySearch2(arr, target, left, mid - 1);
    }
    return -1;
}

C 实现

1
2
3
4
5
6
7
8
9
int binary_search(int* a, int left, int right, int target) {
    while(left <= right){
        int mid = (left + right) / 2;
        if(a[mid] == target) return mid;
        if(a[mid] < target) left = mid + 1;
        else right = mid - 1
    }
    return -1;
}

References

https://en.wikipedia.org/wiki/Binary_search_algorithm