原題
給出一個目標數(shù)字和一個整數(shù)升序數(shù)組漾橙，找到一個i使得A[i]與目標數(shù)字最為接近。
- 給出 [1, 2, 3] 并且 target = 2, 返回 1
- 給出 [1, 4, 6] 并且 target = 3, 返回 1
- 給出 [1, 4, 6] 并且 target = 5, 返回 1 or 2
- 給出 [1, 3, 3, 4] 并且 target = 2, 返回 0 or 1 or 2
解題思路
- 二分法友鼻，直接找target，找到返回index，如果沒有找到則target在A[start]和A[end]之間，比較之后品腹，返回正確的index
完整代碼
class Solution:
# @param {int[]} A an integer array sorted in ascending order
# @param {int} target an integer
# @return {int} an integer
def closestNumber(self, A, target):
# Write your code here
if not 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
return start if abs(A[start] - target) < abs(A[end] - target) else end
