二分法查找(C-C++实现)

Tue Sep 5, 2017

200 Words|Read in about 1 Min
Tags: 算法  

封装成函数:

//二分法查找
//数组a是升序的,len为数组长度
//k为待查找的整数
//如果查到有就返回对应角标,
//没有就返回-1
int search(int *a,int len, int k)
{
    int lo = 0, hi = len - 1;
    while (lo <= hi)
    {
        int m = (lo + hi) >> 1;
        if (a[m] < k)
        {
            lo = m + 1;
        }
        else if (a[m] > k)
        {
            hi = m - 1;
        }
        else
        {
            return m;
        }
    }
    return -1;
}

测试:

int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int len = sizeof(a)/sizeof(int);
printf("%d\n",search(a,len,6));

输出: 6

See Also

Tue Sep 5, 2017

200 Words|Read in about 1 Min
Tags: 算法