Description
Find any position of a target number in a sorted array. Return -1 if target does not exist.
Have you met this question in a real interview? Yes
Example
Given [1, 2, 2, 4, 5, 5].
For target = 2, return 1 or 2.
For target = 5, return 4 or 5.
For target = 6, return -1.
Challenge
O(logn) time
class Solution:
"""
@param: nums: An integer array sorted in ascending order
@param: target: An integer
@return: An integer
"""
def findPosition(self, nums, target):
# write your code here
if not nums:
return -1
start = 0
end = len(nums) -1
while (start + 1) < end:
mid = start + (end - start)//2
if nums[mid] == target:
# find the last position
end = mid
if nums[mid] < target:
start = mid
else:
end = mid
if nums[end] == target:
return end;
if nums[start] ==target:
return start
else:
return -1
