开源时代C语言C++

查找算法——二分查找

2017-10-12  本文已影响18人  NiceBlueChai

二分查找,也称折半查找
目的:提高查找速度(当查找性能成为问题时,考虑使用二分查找)

使用前提:(较为严格)
已经排好序(升序或降序)的数组

算法思想
每次跟中间元素mid比较,如小于mid,则在前半部分;若大于mid,则在后半部分,若等于mid,则查找完成。

示例代码

//增序排列的二分查找
int bin_find(const int arr[], int len, int val)
{
    int low = 0;
    int hight = len - 1;
    while (low<=hight)
    {
        int mid = (hight + low) / 2; //中间位置
        if (arr[mid] == val)
        {
            return mid;//找到了
        }
        else if(arr[mid]>val)
        {
            hight = mid - 1;//比中间项小,则在左侧
        }
        else
        {
            low = mid + 1;//比中间项大,则在右侧
        }
    }
    return -1;
}

int main()
{
    int data[8] = { 54,0xa1,0x7f,12,10,9,98,119 };

    int bin_num = bin_find(data, 8, 12);

    return 0;
}
  • 与遍历查找比较
    查找速度优于遍历查找,
    最多查找log2(N)次
    最少查找1次

❤️


上一篇 下一篇

猜你喜欢

热点阅读