【数据结构】| 二分查找

275 阅读2分钟

二分查找是一种效率较高的查找方法,时间复杂度是O(logn)

二分查找:每次都通过跟区间中的中间元素对比,将待查找的区间缩小为一半,直到找到要查找的元素,或 者区间被缩小为0

使用前提:

  1. 二分查找必须依赖顺序表结构(数组)
  2. 二分查找查询的数据必须是有序的

关于查询数据的大小,如果查询的数据太小,直接遍历就可以,两者效率相差不大,如果要查找的数据太大,因为二分查找必须依赖顺序表结构,所以需要申请的空间必须是连续的,有可能会出现没有足够的连续内存空间的情况

实现:

数组arr:{1,4,7,8,12,43,56,87,98,323,3545,5685},利用二分查找返回数组下标

例:查找43输出5

public static int binary(int[] arr, int n){
    int start = 0;
    int end = arr.length - 1;
    while (start<=end){
        int mid = (start + end)/2;
        if(arr[mid]== n){
            return mid;
        } else if (n > arr[mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

递归实现:

public static int binary(int[] arr, int n, int start, int end){
    if(start > end){
        return -1;
    }
    int mid = (start + end)/2;
    if(arr[mid] == n){
        return mid;
    } else if (n > arr[mid]) {
        return binary(arr, n, mid + 1, end);
    } else {
        return binary(arr, n, start, mid - 1);
    }
}

当数组中没有重复数据时,可以使用上述方法,但是有些需求可能是数组中有重复数据,需要查找数组中某个数的第一次出现的下标

例:数组{1,4,7,43,43,43,56,87,98,323,3545,5685},查找43输出3

public static int binary(int[] arr, int n){
    int start = 0;
    int end = arr.length - 1;
    while (start<=end){
        int mid = (start + end)/2;
        if(arr[mid] == n && mid>0 && arr[mid -1] != n ){
            return mid;
        } else if (n > arr[mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}