二分查找

前提条件是已经排好序的序列。

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;


// 如下写法的比较
//right=n-1 => while(left <= right) => right=middle-1;
//right=n   => while(left <  right) => right=middle;
int binary_search(int array[], int n, int value)
{
    int left = 0;
    int right = n-1;
    while(left <= right)
    {
        int middle = ((right - left) >> 1) + left; // 防止溢出的写法，同时middle在循环内，随时更新。

        if(array[middle] > value)
            right = middle -1;               //right 随写法的不同，赋值的情况就随机应变

        else if(array[middle] < value)
            left = middle + 1;

        else
            return middle;      // 相等情况的判断放在最后，大多数情况下判断不相等的情况较多，这样减少判断的次数。
    }
    return -1;
}

int main()
{
     int array[10]={3,4,1,10,5,8,9,12,20,12};
     sort(array,array+10);
     cout<<binary_search(array, 10, 12)<<endl;
	 return 0;
}

应用：

剑指offer：数字在排序数组中出现的次数