NC105 二分查找-II

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        boolean find = false;
        while(left<=right){
            mid = (left + right)>>1;
            if(nums[mid] == target) {find = true; break;}
            else if(nums[mid] > target) right = mid-1;
            else left = mid +1;
        }
        if(!find) return -1;
        while(mid>0 && nums[mid]==nums[mid-1]) mid--;
        return mid;
    }
}

import java.util.*;


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

    public int halfsearch(int[] nums, int left, int right, int target){
        while(left<=right){
            int  mid = (left + right) >> 1;
            if(nums[mid] == target){
                while(mid >= 1 && nums[mid-1] == target ){
                    mid--;
                }
                return mid;
            }else if(nums[mid]>target){
                return halfsearch(nums, left, mid-1, target);
            }else{
                return halfsearch(nums, mid + 1, right, target);
            }
        }
        return -1;
    }
}

递归费劲了
下面的是不需要递归的

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left<=right){
            int  mid = (left + right) >> 1;
            if(nums[mid] == target){
                while(mid >= 1 && nums[mid-1] == target ){
                    mid--;
                }
                return mid;
            }else if(nums[mid]>target){
                right = mid-1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }

}

下面的占用内存小

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;
    }
}