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

二分(折半)查找

程序员文章站 2022-03-14 20:35:14
...

前提条件:
List——一个元素有序存放的线性列表;
k——待查找的元素。
二分查找法的原理是:这里假设List是按照递增顺序排列,对于给定的关键字k,比较k和处于List的中间位置的元素的大小关系,根据这个大小关系来确定k是在List的中间还是在List的前半段或后半段,以此类推,知道找到元素k或者查找失败。
C++实现:

/*----------------------------------------
Array是存储待查找元素的数组
length是数组的长度或者说是待查找序列的元素个数
item是待查找的元素
----------------------------------------*/
void binarySearch(int* Array, int length, int item) {
    if (Array == NULL)
        return;
    int first = 0,
        last = length - 1,
        mid;
    bool found = 0;

    while (first <= last && found == false) {
        mid = (first + last) / 2;
        if (item > Array[mid]) {
            first = mid + 1;
        }
        else if (item < Array[mid]) {
            last = mid - 1;
        }
        else if(item == Array[mid]) {
            cout << mid << endl;//输出item在Array中的索引号(以0开始)
            found = true;
        } 
    }
}