原題
Given a big sorted array, find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number.
Return -1, if the number doesn't exist in the array.
解題思路
- 二分查找
- 由于有重復(fù)數(shù)字時(shí)煮剧，返回第一個(gè)出現(xiàn)的index鄙皇，所以
A[mid] == target時(shí)搓幌，end = mid - 由于數(shù)組非常大强胰，所以我們希望用一種方式找到剛剛好比target大一些的數(shù)作為end，代碼如下：
end = 0
while end < len(A) and A[end] < target:
end = end * 2 + 1
if end >= len(A):
end = len(A) - 1
完整代碼
class Solution:
# @param {int[]} A an integer array
# @param {int} target an integer
# @return {int} an integer
def searchBigSortedArray(self, A, target):
if not A:
return -1
end = 0
while end < len(A) and A[end] < target:
end = end * 2 + 1
if end >= len(A):
end = len(A) - 1
start = 0
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] >= target:
end = mid
else:
start = mid
if A[start] == target:
return start
elif A[end] == target:
return end
return -1
