0704. 二分查找 #
- 标签:数组、二分查找
- 难度:简单
题目大意 #
描述:给定一个升序的数组 nums
,和一个目标值 target
。
要求:返回 target
在数组中的位置,如果找不到,则返回 -1。
说明:
- 你可以假设
nums
中的所有元素是不重复的。 n
将在[1, 10000]
之间。nums
的每个元素都将在[-9999, 9999]
之间。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:二分查找 #
设定左右节点为数组两端,即 left = 0
,right = len(nums) - 1
,代表待查找区间为 [left, right]
(左闭右闭)。
取两个节点中心位置 mid
,先比较中心位置值 nums[mid]
与目标值 target
的大小。
- 如果中心位置值
nums[mid]
与目标值target
相等,则返回中心位置。 - 如果中心位置值
nums[mid]
小于目标值target
,则将左节点设置为mid + 1
,然后继续在右区间[mid + 1, right]
搜索。 - 如果中心位置值
nums[mid]
大于目标值target
,则将右节点设置为mid - 1
,然后继续在左区间[left, mid - 1]
搜索。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(\log_2n)$。
- 空间复杂度:$O(1)$。