算法从二分开始0——在循环体内部查找元素｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述：

二、思路分析：

已知：升序，进而可以推断出不重复。

这就很好办了，一个简单的二分。

那么，我们该如何写二分呢？

while (left < right )
or
while (left <= right)

if(arr[mid] < target)
or
if(arr[mid] <= target)
复制代码

这些细节很容易困扰我们，但我不会在这篇文章直接给出准确答案。而是告诉你具体问题具体分析

三、AC 代码：

public int search(int[] nums, int target) {
    int len = nums.length;
    // 考虑下空数组的情况
    if (len == 0) {
        return -1;
    }
    int left = 0;
    int right = len - 1;
    
     while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            // 由数组的有序性可知，mid 以及 mid 的左边都小等于 target
            // 下一轮搜索的范围是 [mid + 1, right]
            left = mid + 1;
        } else {
            // 此时 target < nums[mid]
            // 由数组的有序性可知，mid 以及 mid 的右边边都小等于 target
            // 下一轮搜索的范围是 [left, mid - 1]
            right = mid - 1;
        }
    }
    return -1;
}
复制代码

四、总结：

首先是对于if的条件，如果有的时候有重复项，让你寻找第一个target/最后一个target。要怎么去设置if条件呢？arr[mid] == target以后要怎么操作？

个人不建议在这个时候将三个if判断合并为两个，保留框架本身，能让你把更多的经历用在思考题意上。

这是一个很基础的框架，除了判空以外，你需要注意三点：

1. while条件，这决定你什么时候停止查找
2. if条件，建议是分为== > < 三个部分来写，我当然知道有的时候可以融合到一起成为两个部分，但这样会让你失去对框架的把握，新手不建议这样。
3. mid = left + (right – left)/2 这么写可能会导致永远也取不到右边界（比如len = 2的时候）