Closest Number In Sorted Array

Description

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.

Challenge

O(logn) time complexity.

Related problems

K Closest Numbers In Sorted Array

Last Position of Target

Classical Binary Search

First Position of Target

Implementation

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

class Solution {
public:
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    int closestNumber(vector<int>& A, int target) {
        // Write your code here
        if(A.size() == 0) return -1;

        int left = 0, right = A.size() - 1;
        while(left + 1 < right) {
            int middle = left + (right - left) / 2;
            if(A[middle] > target) {
                right = middle;
            } else if(A[middle] == target) {
                return middle;
            } else {
                left = middle;
            }
        }

        if(abs(A[left] - target) > abs(A[right] - target)) {
            return right;
        } else {
            return left;
        }
    }
};