Closest|Closest Number in Sorted Array
题目描述
Given a target number and an integer array A sorted in ascending order, find the indexiin A such that A[i] is closest to the given target.
Return -1 if there is no element in the array.
Notice
There can be duplicate elements in the array, and we can return any of the indices with same value.
Example
Given[1, 2, 3]and target =2, return1.
Given[1, 4, 6]and target =3, return1.
Given[1, 4, 6]and target =5, return1or2.
Given[1, 3, 3, 4]and target =2, return0or1or2.
【Closest|Closest Number in Sorted Array】代码
public class Solution {
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
public int closestNumber(int[] A, int target) {
// Write your code here
if (A == null || A.length == 0) {
return -1;
}int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if(target== A[mid]) {
return mid;
} else if (target < A[mid]) {
end = mid;
} else {
start = mid;
}
}return (Math.abs(A[start] - target) < Math.abs(A[end] - target)) ? start : end;
}
}
推荐阅读
- LintCode|LintCode 545 [Top k Largest Number II]
- 136.|136. Single Number
- 兼容性处理
- 基本包装类型
- ZOJ-3447---Doraemon's Number Game (贪心+大数）
- 数论|Codeforces 235E Number Challenge 莫比乌斯反演+数论
- FZU-2109 Mountain Number(数位dp)
- 力扣--Letter Combinations of a Phone Number
- 快乐数|快乐数 (lintcode:happy-number)
- #|我的Android进阶之旅------>Android自定义View实现带数字的进度条（NumberProgressBar）