原题
给出一个目标数字和一个整数升序数组，找到一个i使得A[i]与目标数字最为接近。
- 给出 [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
