OJ lintcode 二分查找

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
您在真实的面试中是否遇到过这个题？
Yes
样例
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

class Solution {
public:
    /**
     * 这个题不难, 很常见,但是有点卡顿
     * 问题:
     * 1. vector 是可以按照下标访问的,下标的顺序是 0~size()-1
     * 2.对于递归函数的设计思路,一定要想清楚它的终止条件
     * 
     * 终止:
     *  1. 如果begin,和end挨在一起,即(end-begin<=1),
     *          1. 但是还没有找到 end和begin都不是target  返回-1
     *          2. end 和begin 有一个是 target  ,返回下标
     *  2. mid=(end+begin)/2  a[mid]==target  
     *          看一下mid前面的元素是不是target
     *          然后返回下标
     * 
     * @param nums: The integer array.
     * @param target: Target number to find.
     * @return: The first position of target. Position starts from 0. 
     */
    int bin_search(vector<int> &a,int begin,int end,int target){
        if(end-begin<=1){
            if(a[begin]==target){
                return begin;
            }
            if(a[end]==target){
                return end;
            }
            //没有命中
            return -1;
        }
        else{
            int mid=(begin+end)/2;
            if((a[mid])==target){
                //命中
                //找到最前面的元素的下标
                while(a[mid]==target){
                    mid--;
                }
                mid++;
                return mid;
            }
            else{
                if((a[mid])<target){
                    bin_search(a,mid,end,target);
                }
                else
                {
                    bin_search(a,begin,mid,target);
                }
            }
        }
    }
    int binarySearch(vector<int> &array, int target) {
        // write your code here
        int begin=0;
        int end=array.size()-1;
        return bin_search(array,begin,end,target);

    }
};