二分查找-力扣(Java)

题目描述

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

简要描述二分法

首先应为一个有序数列，我们将会数字设定为一个数组nums，将要在数组中寻找的目标设置为target。在数组中，对数组中间值nums[middle]与target进行判断，并对其进行空间的压缩，然后再次判断新的nums[middle]与target的大小关系，直到nums[middle]与target相等为止

思路

1. 首先明确题目要求，为寻找目标值，若存在返回下标，不存在则返回-1，标准的二分查找
2. 明确了二分查找要求后，确定使用左闭右闭还是左闭合又开，即选择[left,right]还是[left,right)，这里我选择的是左闭右闭
3. 确定了使用左闭右闭写法之后，便应该明确怎么写代码。由于目标值在[left,right]区间，所以while(left ? right)中？处应填写<= ,因为在[left,right]区间中,left == right是存在的，例[1,1]，所以应当使用<=
4. 同时判断语句if (nums[middle] > target) 时,由于middle大于目标值，所以即目标值出现在左半边，所以应当将right(即右边界)赋值为middle – 1，因为判断条件为if (nums[middle] > target)，此时的nums[middle] 必然不是目标值，所以可以自然往左一位
5. 而判断语句if (nums[middle] < target)时，由于middle小于目标值，所以即目标值出现在右半边，所以应当将left(即左边界)赋值为middle + 1，原因参考上一点
6. 当nums[middle] = tarage 时，直接return middle输出结果即可
7. 最后在while循环外写入return -1表示目标值不存在即可

代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0 ;
        int right = nums.length -1;
        while(left <= right){
            int middle = left + (right - left) / 2;
            if(nums[middle] > target)
                right = middle -1;
            else if(nums[middle] < target)
                left = middle + 1;
            else if(nums[middle] == target)
            return middle;
        }
        return -1;
    }
}

提交截图