java中二分查找的思想是什么?算法实例展示

BSO 2020-09-15 14:39:11 java常见问答 3305

在我们学习java的过程中有时会遇到一些问题,它们对于我们的学习来说是一个锻炼的机会。今天就来为大家介绍java中二分查找的思想是什么以及它的算法实例展示。一起来看看吧。

一、 基本思想

二分查找的基本思想是,假设R[low..high]是当前的查找区间

1.首先确定该区间的中点位置:mid=[﹝low+high﹞/2]

2.然后将待查的K值与R[mid].key比较。如果相等,那么查找成功并返回此位置,不然的话就要确定新的查找区间,继续二分查找,具体方法如下:

⑴如果R[mid].key>K,那么由表的有序性可以知道R[mid..n].keys均大于K,因此如果表中存在关键字等于K的结点,那么这个结点必定是在位置mid左边的子表R[1..mid-1]中,所以新的查找区间是左子表R[1..mid-1]。

⑵如果R[mid].key<k,那么要查找的k必在mid的右子表r[mid+1..n]中,也就是新的查找区间是右子表r[mid+1..n]。下一次查找是针对新的查找区间进行的。

总而言之,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可以确定查找是否成功,不成功那么当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。

再补充一点,二分查找只适用顺序存储结构。

二分查找算法实例代码展示:

/*折半查找*/
int Binary_Search(int a * , int n, int key)
{
    int low, high, mid;
    low = 1; /*定义最底下标为记录首位*/
    high = n; /*定义最高下标为记录末位*/
    while (low <= high)
    {
        mid = (low + high) / 2; /*折半*/
        if (key < a[mid])
            high = mid - 1;
        if (key > a[mid])
            low = mid + 1;
        else
            return mid;
    }
    return 0;
}

另外一种构造参数:

int BinSearch(SeqList R, KeyType K)
{
    //在有序表R[1..n]中进行二分查找,成功时返回结点的位置,失败时返回零
    int low = 1;
    int high = n;
    int mid;
    //置当前查找区间上、下界的初值
    while (low <= high)
    //当前查找区间R[low..high]非空
    {
        mid = (low + high) / 2;
        if (R[mid].key == K)
            return mid;
        //查找成功返回
        if (R[mid].kdy > K)
            high = mid - 1;
        //继续在R[low..mid-1]中查找
        else
            low = mid + 1;
        //继续在R[mid+1..high]中查找
    }
    return 0;
    //当low>high时表示查找区间为空,查找失败
}

以上就是关于java中二分查找的思想以及算法实例展示的主要内容。如果你对java知识感兴趣,想要了解更多java经典例子以及常见问题,敬请关注奇Q工具网。

推荐阅读:

javac的结构是怎样的?它的查找类型包括哪些内容?

java Collections类操作集合查找、替换操作详解

二分法查找(思路和实现),二分法查找是什么?