分治法

1、二分搜索算法

   前提条件：搜索的序列本身有序。

#include <iostream>
using namespace std;

//在数组a(0,....n-1)中搜索x，找到x时返回它在数组中的下标，否则返回-1
template <class Type>
int BinarySearch(const Type a[], const Type &x, int n)
{
    int left = 0, right = n-1;
    int mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (a[mid] == x)
        {
            return mid;
        }
        else if (a[mid] > x)
        {
            right = mid - 1;
        }
        else if (a[mid] < x)
        {
            left = mid + 1;
        }
    }
    return -1; //未找到x
}

int main()
{
    int arr[10];
    for (int i = 0; i < 10; i++)
    {
        arr[i] = i + 1;
    }
    int index = BinarySearch(arr, 33, 10);
    cout<<index<<endl;

    return 0;
}

整个算法的最坏时间复杂性为O(logn)。在查找不成功的情况，共比较的次数为：