牛客——二分查找Ⅰ和Ⅱ题序NC105、160

也叫折半查找

NC160

无重复数字的升序数组的二分查找

public int search (int[] nums, int target) {
        // write code here
        int left = 0, right = nums.length - 1;
        int temp;
        while (left <= right){
             temp = (left + right)/2;
            if (nums[temp] == target){
                return temp;
            }else if (nums[temp] < target){
                left = temp + 1;
            }else {
                right = temp - 1;
            }
        }
        return -1;
    }

//也可以用递归的方法，不过方法参数要增加两项，即分出来的左右边界left,right

//折半查找-有序数组
    public int find(int[] nums, int left, int right, int target){
        int temp = (left + right)/2;
        if (left > right){
            return -1;
            return;
        }
        if (nums[temp] == target){
            return temp;
        }else if(nums[temp] > target){
            find(nums, left, temp - 1, target);
        }else{
            find(nums, temp + 1, right, target);
        }
    }

NC105

有重复数字的升序数组的二分查找

int right = nums.length - 1, left = 0, temp;
        while (left <= right){
            temp = (left + right)/2;
            if (nums[temp] == target){
            	//添加这一句while即可，找到target之后往前找到相等的第一个出现的位置，注意判断越界问题
                while((temp - 1 >= 0) && (nums[temp-1] == nums[temp]))temp = temp - 1;
                return temp;
            }else if (nums[temp] < target){
                left = temp + 1;
            }else {
                right = temp - 1;
            }
        }
        return -1;