http://www.lintcode.com/en/problem/closest-number-in-sorted-array/

Given a target number and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to the given target.

Return -1 if there is no element in the array.

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, return 1. Given [1, 4, 6] and target = 3, return 1. Given [1, 4, 6] and target = 5, return 1 or 2. Given [1, 3, 3, 4] and target = 2, return 0 or 1 or 2.

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 lo = 0;
        int hi = A.length - 1;
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[mid] < target) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        if (Math.abs(A[lo] - target) < Math.abs(A[hi] - target)){
            return lo;
        }
        return hi;
    }
}