题目大意
#
给定一个升序的数组 nums,和一个目标值 target,返回 target 在数组中的位置,如果找不到,则返回 -1。
解题思路
#
纯粹考察二分查找。
算法基本原理:
设定左右节点为数组两端。不断判断两个节点中心位置与目标值的大小。
- 如果中心位置与目标值相等,则返回中心位置。
- 如果中心位置小于目标值,则将左节点设置为中心位置+1,然后继续在右侧搜索。
- 如果中心位置大于目标值,则将右节点设置为中心位置-1,然后继续在左侧搜索。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
ans = -1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
ans = mid
left = mid+1
return ans
if nums[mid] < target:
left = mid+1
else:
right = mid-1
return ans
|