题解 | #二分查找-II#

JAVA
二分法的思想:
思路：设置三个哨兵位置(min max mid)
初始时候mid = (min +max)/2 的位置
然后用被查找的对象数和mid去比较，
如果大于mid，则表示对象数在mid的右侧，此时更新查找范围，把min变为mid+1 （此处用数组下标说明）
如果小于mid，则表示对象数在mid的左侧，此时更新查找范围，把max变为mid-1 （此处用数组下标说明）
※注意是要找到有序数组中第一个匹配的下标，所以这里应该是要在min~ mid之间。
测试用例[1,2,2,3,4],2的时候，最开始找到的是下标为2的2， 题目是要返回下标是1 的2

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int index = -1;
        int min = 0;
        int max = nums.length -1;
        int mid = 0;
        while(min <= max){
            mid = min + (max - min)/2;
            // 如果小于mid，则表示对象数在mid的左侧，此时更新查找范围，把max变为mid-1
            if(nums[mid] > target)  //
                max = mid-1;
            // 如果大于mid，则表示对象数在mid的右侧，此时更新查找范围，把min变为mid+1
            else if(nums[mid] < target)
                min = mid+1;
            //找到,但不一定是第一个出现的，
            else {
                index = mid;
                //要再min ~ mid之间找到第一个出现的。
                max = mid -1; 
            }
        }
        //未找到
        return index;
    }
}