欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分法查找

程序员文章站 2022-06-11 18:57:05
...

二分查找又称二分查找。
如果是在一个元素排列有序的数组中进行查找,可以采用折半查找。
二分查找的基本思想是:对于已知的按关键字排序的序列,经过一次的比较后,可将序列分割成两部分,然后只在有可能包含待查找元素的一部分中接着查找,并根据试探结果继续分割,逐步缩小查找范围,直到找到或找不到为止。
二分查找的具体图解
二分法查找
代码如下;

#include<iostream>
#include<algorithm>
using namespace std;
//  折半查找的方法,在元素升序排列的数组list中查找值为k的元素
int binSearch(int list[],int n,int k)
{
    int low=0;
    int high=n-1;
    while(low<=high)//如果low<=high 表示整个数组尚未查找完
    {
        int mid=(low+high)/2;//求中间元素的下标
        if(k==list[mid])
            return mid;//找到k 返回下标
        else if(k<list[mid])
            high=mid-1;//若k<list[mid]将范围缩小到前一半
        else
            low=mid+1;//若k>list[mid]将范围缩小的后一半
    }
    return -1;//若找不到 返回-1
}
int main()
{
    int list[]={1,2,3,4,5,6};
    cout<<binSearch(list,5,5)<<endl;
    return 0;
}