二分查找
难度:
标签:
题目描述
代码结果
运行时间: 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`?
▷🦆
为何在判断`nums[mid]`与`target`的关系后,选择将`hi`设置为`mid - 1`而不是`mid`?
▷🦆
在题解中,为什么最后需要检查`lo`是否在数组范围内以及`nums[lo]`是否等于`target`?
▷🦆
如果`nums`数组为空,这个算法会如何处理?
▷