LintCode Q14 First Position of Target in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月14日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
# @param nums: The integer array
# @param target: Target number to find
# @return the first position of target in nums, position start from 0
def binarySearch(self, nums, target):
# write your code here
# [1, 2, 3, 3, 4, 5, 10]
lo = 0
hi = len(nums) - 1
possible = None
while lo <= hi:
mi = lo + (hi - lo)/2
if nums[mi] < target:
lo = mi + 1
elif nums[mi] > target:
hi = mi - 1
else:
possible = mi
break
if possible is None:
return -1
while possible >= 0 and nums[possible] == target:
possible -= 1
return possible + 1
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。