For a given sorted array (ascending order) and atargetnumber, find the first index of this number inO(log n)time complexity.

If the target number does not exist in the array, return-1.

Example

If the array is[1, 2, 3, 3, 4, 5, 10], for given target3, return2.

分析： 这题可以套用二分法模板， 关键是题目要求是找出“第一个”符合条件的index，所以找到mid = target的时候，不能直接assume这个mid是第一个index， 只能end = mid继续循环找下去， 直到 start + 1 == end，然后先判断start， 后判断end

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {


     if(nums == null || nums.length == 0){
            return -1;
        }

        int start = 0;
        int end = nums.length-1;

        while(start + 1 < end){
            int mid = start + (end - start)/2;
            if(nums[mid] < target){
                start = mid;
            }else if (nums[mid] >= target){
                end = mid;
            }
        }

        if(nums[start] == target){
            return start;
        }else if(nums[end] == target){
            return end;
        }

        return -1;

    }


}