题解 | #二分查找-II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {

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

        int len = nums.length;
        int low = 0;
        int high = len - 1;

        return searchTwo(target, low, high, nums);
    }

    public int searchTwo(int target, int low, int high, int[] nums){

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (nums[mid] == target) {
                high = mid - 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        /**
         * 1:[]情况 直接返回-1
         * 2:[1,2,2,4]情况
         * mid = (0+3)/2 = 1 nums[1] = 2 命中 high = mid - 1 = 0
         * 再次循环 mid = (0 + 0)/2 = 0 nums[0]=1 < target:2 命中 low = mid + 1 = 1
         * 此时low = 1 high = 0 不满足while循环low<=high逻辑 跳出while循环
         * 注意:此时在搜索左边界无果的情况下low 跳回了上一步命中nums[mid] = target时,mid下标的位置
         * 所以此时判断if nums[low] = target 即是数组中第一次出现target的位置
         * 
         * 3:如果target=3 那么会命中 mid = 1 high = 0 high = -1 不满足Low<=high 跳出循环
         * 也不满足nums[low] = target的逻辑 所以直接返回-1
         *
         */
        if (nums[low] == target) {
            return low;
        }

        return -1;
    }
}