各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

Catalog

    二分查找与二分答案(1)

    June 12, 2018 • Read: 524 • 算法

    我们在写程序的时候,经常会遇到这样一类问题:在一个数组中查找一个数是不是存在。比如在下图的数组中,查找8是不是存在:
    image
    如果不要求效率,我们最一般的查找方法就是顺序查找,依次查看a[0], a[1], …, a[n-1],检查是不是等于8。这样对于长度为n的数组,平均查找长度是n/2

    如果数组是有序的,比如是递增的,就像上图[1, 2, 3, 4, 5, 7, 8, 10, 11, 13]一样的话。我们就有效率更高的查找算法,叫做二分查找。例如还是在上面数组中查找8


    第一步:我们直接找位于中间的数a[4],发现a[4]=5,比8要小,所以如果8在这个数组里,肯定在a[5]~a[9]之中

    第二步:我们找a[5]-a[9]这个范围里位于中间的数a[7],发现a[7]=10,比我们要找的数大,所以如果8在这个数组里,肯定在a[5]-a[6]之中

    第三步:我们找a[5]~a[6]这个范围里位于中间的数a[5],发现a[5]=7,比我们要找的8小。所以我们知道如果8在数组里,那它肯定是a[6]这个数

    第四步也是最后一步。我们查看a[6]的值,发现a[6]=8,于是我们找到了8的位置。假如我们这时发现a[6]不是8,则说明8没有在这个数组里

    二分查找又叫“折半查找”。因为我们每进行一步,也就是查看一个元素的数值,都会使得后面需要检查的范围缩小一半

    二分查找的时间复杂度是O(logN)的,换句话说,在长度为N的有序数组中查找一个数,查看元素的次数最多是logN+1次。当N很大时,二分查找的速度比顺序查找快非常多倍

    #include<iostream>
    using namespace std;
    int n,x,a[1000000];
    int binary_search(int a[],int n,int x)
    {
        int l = 0;
        int r = n - 1;
        int ans = -1;
        while(l <= r)
        {
            int m = (l + r) / 2;
            if(a[m] == x)
            {
                ans = m;
                break;
            }
            if(a[m] < x)
                l = m + 1;
            else
                r = m - 1;
        }
        return ans;
    } 
    int main()
    {
        cin >> n >> x;
        for(int i = 0;i < n;i++)
            cin >> a[i];
        int ans = binary_search(a,n,x);
        cout << ans;
        return 0;
    }
    Archives Tip
    QR Code for this page
    Tipping QR Code
    Leave a Comment