C++实现二分查找

发表于 分类于

二分查找又称折半查找，二分查找是针对有序数组所用的一种快速查找元素的方法。

二分查找的条件及优缺点

条件：针对有序数组（元素从小到大或从大到小）
优点：查询速度较快，时间复杂度为O（n）
缺点：有硬性条件的限制，而且即使查到后，插入与删除困难。

二分查找的图解

img

二分查找的C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;

int binarySearch(const int *array, int aSize, int key)
{
    if ( array == nullptr || aSize == 0 )
        return -1;
    int low = 0;
    int high = aSize - 1;
    int mid = 0;

    while ( low <= high )
    {
        mid = (low + high )/2;

        if ( array[mid] < key)
            low = mid + 1;
        else if ( array[mid] > key )
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}

int main() {

    int array[50];
    for (int i=0; i<50; i++)
        array[i] = i;

    cout<<"pos = "<<binarySearch(array, 50, 17)<<endl;

    return 0;
}