二分查找

//数组增序减序无所谓
class BinarySearch {
public:
    int getPos(vector<int> A, int n, int val) {
        if(n<=0) return -1;
        int left = 0,right = n-1;
        while(left<=right)
        {
            int mid = (left+right)/2;
            if(val == A[mid])
            {
                int i = mid-1;
                for(;i>=0&&val == A[i];i--);

                return i+1;
            }
            else if(val>A[mid]) 
                left = mid+1;
            else
                right = mid -1;
        }
        return -1;
    }
};