lintcode 14. First Position of T

二分查找：
要注意为了寻找第一个，所以要继续往前推

class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    int binarySearch(vector<int> &nums, int target) {
        // write your code here
        if(nums.size() == 0) return -1;
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            cout<<mid<<endl;
            if(nums[mid] == target){
                int index = mid;
                while(index-1 >= 0 && nums[index-1] == target){
                    index--;
                };
                return index;
            }
            if(nums[mid] < target) left = mid+1;
            else right = mid - 1;
        }
        return -1;
    }
};

解法二：lowbound upperbound
class Solution {
public:
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
int binarySearch(vector<int> &nums, int target) {
// write your code here
if(nums.empty()) return -1;
int lb = -1;
int ub = nums.size();
while(lb + 1 < ub){
int mid = lb + (ub - lb) / 2;
if(nums[mid] < target ) lb = mid;
else ub = mid;
}
if(nums[lb + 1] == target) return lb + 1;
return -1;
}
};

注意这种方法，要让target > nums[mid]
所以最后返回的nums[mid] 是 该放置target的第一个位置，如果是target,则找到，如果不是，则返回-1;