二分查找算法

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

算法

  1. 假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;
  2. 否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
  3. 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

算法要求

  1. 必须采用顺序存储结构。
  2. 必须按关键字大小有序排列。

复杂度

时间复杂度

折半搜索每次把搜索区域减少一半,时间复杂度为 O(logn)。(n代表集合中元素的个数)

空间复杂度

O(1)。虽以递归形式定义,但是尾递归,可改写为循环。

代码示例

java

循环

public static int binarySearch(int[] arr, int start, int end, int hkey){
    int result = -1;
    while (start <= end){
        int mid = start + (end - start)/2;
        if (arr[mid] > hkey)
            end = mid - 1;
        else if (arr[mid] < hkey)
            start = mid + 1;
        else {
            result = mid ;  
            break;
        }
    }
    return result;
}

递归

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

python

def binary_search(arr, start, end, hkey):
    if start > end:
        return -1
    mid = start + (end - start) / 2
    if arr[mid] > hkey:
        return binary_search(arr, start, mid - 1, hkey)
    if arr[mid] < hkey:
        return binary_search(arr, mid + 1, end, hkey)
    return mid

【腾讯云】境外1核2G服务器低至2折,半价续费券限量免费领取!
https://cloud.tencent.com/act/cps/redirect?redirect=1068&cps_key=e4b50f6c64a4480367f8a8d16fd07c5a&from=console

标签: java, 二分查找算法

添加新评论