二分的两种重要模型

具体见我大哥的小博客

二分最重要的：1.当前待查找序列，肯定包含目标元素 2.每次待查找序列的规模都会变小。
①：0000001111111，寻找一个满足条件的最左；
code：

int binary_search(int array[],int key)
{
    int begin=0;
    int end=array.size();
    while(begin<end)
    {
        int mid=begin+(end-begin)/2;
        if(a[mid]==1)
            end=mid;
        else
            begin=mid+1;
    }
    return begin;
}

②：对于1111000000，寻找一个满足条件的最右；
code……

int binary_search(int array[],int key)
{
    int begin=0;
    int end=array.size();
    while(begin<end)
    {
        int mid=begin+(end-begin+1)/2;
        if(a[mid]==1)
            begin=mid;  //一定会变大
        else
            end=mid-1;  //一定会变小
    }
    return begin;
}