0%

14.二分查找

描述

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
"""
@param nums: The integer array.
@param target: Target to find.
@return: The first position of target. Position starts from 0.
"""
def binarySearch(self, nums, target):
low = 0
high = len(nums) - 1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] == target:
while(mid >= 0):#新增加的while和if用于解决有重复数字的情况,并保证每次都输出第一次出现的target的下标
if nums[mid] != target:
break

mid = mid - 1
if mid <= -1:
return 0
return mid + 1#多减了一次,所以输出时+1
elif target > nums[mid]:
low = mid + 1
else:
high = mid - 1

return -1



nums = [4,5,9,12,13,14,15,15,18]
so = Solution()
print(so.binarySearch(nums,9))