Search

binary search

二分查找法

二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)[1]、对数搜索(英语:logarithmic search)[2],是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;

如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

概览

| 分类 | 搜索算法 |
| 数据结构 | 数组 |
| 最坏时间复杂度 | O(log(n)) |
| 最优时间复杂度 | O(1) |
| 平均时间复杂度 | O(log(n)) |
| 空间复杂度 | 迭代: O(1); 递归: O(log(n)) |

步骤

① 首先确定整个查找区间的中间位置 mid = ( left + right )/ 2

② 用待查关键字值与中间位置的关键字值进行比较;

若相等,则查找成功

若大于,则在后(右)半个区域继续进行折半查找

若小于,则在前(左)半个区域继续进行折半查找

③ 对确定的缩小区域再按折半公式,重复上述步骤。

最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放。

Java 代码实现

  • 循环
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;
}
  • 递归
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;
}

参考资料

二分搜索算法

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html

Please follow and like us:

相关文章 »

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注