力扣 704. 二分查找

1.题目:

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

2.示例:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

3.自己实现:

class Solution {
    public int search(int[] nums, int target) {
        int y =0;
        for(int i =0;i
            if(target == nums[i]){
                return i;
            }
            y++;
        }
        if(nums.length==y){
            return -1;
        }
        return -1;
    }
}

4.优质写法:

总体模板就是先找到中间的数,与目标相比,如果不符合,直接可以砍去一半,在剩下的一半数组里面找

目标数,同理,如果没找到继续砍去剩余一半的一半.这才符合二分寻找

class Solution {
    public int search(int[] nums, int target) {
        //nums.length -1 获取下标
       int left =0; int right = nums.length -1;
       while(left<=right){
            //这里不可以简化为left+right,是因为left和right相加可能会超过int最大值,溢出
            int mid = left+(right - left)/2;
            if(nums[mid]==target){
                return mid;
            //如果中间的数大于目标,那说明target在mid的左侧,那么需要把右侧去掉,也就是right缩小,
                已经判断过target小于mid 所以right = mid -1 
            }else if(nums[mid]>target){
                right = mid -1;
            //如果中间数小于target,那么说明target在mid的右侧,数组越靠右越大,所以要把mid左侧删掉
            left = mid 但是已经判断过mid小于target 所以 left = mid + 1;
            }else{
                left = mid +1;
            }
       }
       return -1;
    }
}