import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标,否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
    // write code here
        int left = 0;
        int mid = 0;
        int right = nums.length - 1;
        int targetIndex = -1;
        while(left <= right){
            mid = left + ((right - left) / 2);
            if(nums[left] == target){
                targetIndex = left;
                break;
            }
            if(nums[right] == target){
                targetIndex = right;
                break;
            }
            if(nums[mid] == target){
                targetIndex = mid;
                break;
            }
            if(left + 1 == right || left == right){
                break;
            }
            if(nums[mid] < target){
                //目标在右侧
                left = mid + 1;
            } else {
                //目标在左侧
                right = mid;
            }
        }
        if(targetIndex != -1){
            //找到了 但不一定是最左侧的
            return findLeftIndex(nums,targetIndex,target);
        } else {
            return -1;
        }
    }

    public int findLeftIndex(int[] nums,int index,int target){
        while(nums[index] == target){
            if(index == 0){
               return index;
            }
            index --;
        }
        return index + 1;
    }
}