14. 二分查找

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
如：在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。
思路：二分查找是基本功，可以写迭代也可以写while循环，目前还是习惯写while循环一些，但是这里的要求和一般的二分查找还不太一样，主要的原因是题目要求查找出第一个，也就是即使找到了一个，也不能立即返回，需要找到第一个才行，我想了一下，有一个思路：找到了把结果赋值给一个变量，然后end更新为mid-1(因为第一个肯定比这个索引小，如果存在的话)，一直把所有的二分查找都找完，返回最新的一个查找的结果就是要求的第一个的索引：

int binarySearch(vector<int> &array, int target) {
        auto beg=array.begin();
        auto end=array.end()-1;
        int res=-1;   //如果这个res最后还是-1的话，就说明没有找到。
        while(beg<=end)
        {
            auto mid=beg+(end-beg)/2;
            if(*mid==target)
            {
            res=mid-array.begin();    //这里是找到了，但不能保证是第一个
            end=mid-1;    //mid仍然更新。
            }
            if(*mid<target)
            beg=mid+1;
            if(*mid>target)
            end=mid-1;
           
        }
        if(res!=-1)
        return res;
        // write your code here
        return -1;
    }

over