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

查找之折半二分法

程序员文章站 2024-03-16 09:18:28
...

1、折半二分法

折半二分法是针对已经排好序的数据,效率比顺序查找快很多。比如2的8次方个数据最多只需要查找8次就能找到了,但是前提是此数据已经排好序了!


2、折半二分法demo

#include <iostream>

using namespace std;

const int n = 10;

template <class T>
void BSearch(T *data, T find, int left, int right);

int main(int argc, const char *argv[])
{
    int data[n] = {1, 2, 3, 4, 5, 88, 99, 100, 101, 110};

    BSearch(data, 2, 0, n);

    BSearch(data, 101, 0, n);

    return 0;
}

template <class T>
void BSearch(T *data, T find, int left, int right)
{
    int mindle;
    mindle = (left + right + 1) / 2;

    if (find == data[mindle]){
        cout << find << " found in data["<< mindle << "]!" << endl;
    }
    else if (find > data[mindle]){
        BSearch(data, find, mindle+1, right);
    }
    else {
        BSearch(data, find, left, mindle-1);
    }
}