原题
在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1
给出数组 [1, 2, 2, 4, 5, 5]
- 对于 target = 2, �返回 1 或者 2.
- 对于 target = 5, �返回 4 或者 5.
- 对于 target = 6, �返回 -1.
解题思路
- 标准的二分法解决 - Binary Search 模板程序
完整代码
class Solution:
# @param {int[]} A an integer array sorted in ascending order
# @param {int} target an integer
# @return {int} an integer
def findPosition(self, A, target):
# Write your code here
if A is None or A == []:
return -1
start, end = 0, len(A) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] == target:
return mid
elif A[mid] > target:
end = mid
else:
start = mid
if A[start] == target:
return start
if A[end] == target:
return end
return -1
