leetcode
leetcode 651 ~ 700
二分查找

二分查找

难度:

标签:

题目描述

代码结果

运行时间: 248 ms, 内存: 16 MB


/*
 * 思路:
 * 使用Java Stream API进行二分查找需要首先将数组转换为List,然后使用带索引的流操作来进行查找。
 * 通过使用IntStream.range来生成索引范围,并过滤出目标值的索引。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int search(int[] nums, int target) {
        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        return IntStream.range(0, list.size())
                        .filter(i -> list.get(i) == target)
                        .findFirst()
                        .orElse(-1);
    }
}

解释

方法:

这个题解使用了二分查找的思路。首先定义了两个指针lo和hi,分别指向数组的开始和结束位置。然后使用while循环不断缩小搜索区间,每次循环都计算中间位置mid,并比较nums[mid]和target的大小。如果相等则直接返回mid;如果nums[mid]大于target,则将搜索区间缩小到[lo, mid-1];如果nums[mid]小于target,则将搜索区间缩小到[mid+1, hi]。循环结束后,如果lo在数组范围内且nums[lo]等于target,则返回lo,否则返回-1。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆
在二分查找中,为什么初始化`hi`的值为`len(nums)`而不是`len(nums) - 1`?
初始化`hi`为`len(nums)`(而非`len(nums) - 1`)是因为,在这种实现中,`hi`始终保持为开区间的一部分(即不包括在搜索区间内)。这样的处理简化了边界条件的处理,避免了一些常见的越界错误。此外,这种处理使得循环可以统一为`while lo < hi`,在循环内部通过调整`lo`和`hi`来缩小搜索范围,而不是担心是否漏掉了边界元素。
🦆
为何在判断`nums[mid]`与`target`的关系后,选择将`hi`设置为`mid - 1`而不是`mid`?
当`nums[mid]`大于`target`时,将`hi`设置为`mid - 1`是为了排除`mid`位置的元素(已知它不等于`target`),从而缩小搜索区间。如果将`hi`设置为`mid`,则下一次循环仍然会考虑`nums[mid]`这个已经知道不是目标的元素,这会导致不必要的重复比较并可能引起循环无法正确终止。
🦆
在题解中,为什么最后需要检查`lo`是否在数组范围内以及`nums[lo]`是否等于`target`?
在二分查找的最后,`lo`可能指向的是目标值`target`应当插入的位置,而这个位置有可能不包含实际的目标值。因此,需要额外检查`lo`指向的位置是否仍在数组范围内以及这个位置的值是否确实等于`target`。这是为了确认最终没有找到目标值的情况下,返回正确的结果(比如`-1`),从而确保算法的准确性和完整性。
🦆
如果`nums`数组为空,这个算法会如何处理?
如果`nums`数组为空,则在算法的初始设置中,`lo`将被初始化为0,而`hi`也为0(因为`nums`长度为0)。因此,`while lo < hi`的条件立即为假,循环不会执行。最终,会执行到最后的返回语句,其中由于`lo`不满足数组范围(即不在0到-1之间),因此会返回`-1`,表示目标值在数组中不存在。

相关问题

搜索长度未知的有序数组

搜索长度未知的有序数组