Find Closest Number in a Sorted Array

Question (LI.459)

Given a target integer and a sorted integer array, return the index that has the closest value to the target.

Does the array have both positive and negative number? Yes. Does the array contain duplicates? Yes. What if two numbers have the same difference? return any index

Example

([1,2,3], 2) => 1
([1,3,3,4], 2) => return either 0,1,2 will be fine
([1,4,6], 5) => return either 1 or 2

Linear Search

Scan the array keep a difference value. Terminate the search once the defference is increasing.

public int closestNumber(int[] A, int target) {
    // edge check
    if (A == null || A.length == 0) {
        return -1;
    }
    // linear search
    int minDiff = diff(A[0], target);
    int i = 1;
    for (i = 1; i < A.length; i++) {
        int curDiff = diff(A[i], target);
        if (curDiff >= minDiff) {
            return i - 1;
        } else {
            minDiff = curDiff;
        }
    }
    // return last index
    return i-1;
}

private int diff(int num1, int num2) {
    return Math.abs(num1 - num2);
}

Linear time O(n)

Binary Search

The array is sorted. We can use an O(1) check to prune half of the search place. This is the only way to beat a linear solution.

O(1) check 3 cases

• A[mid] > target: prune right section, search left section

• A[mid] == target: return mid

• A[mid] < target: prune left section, search right section

public int closestNumber(int[] A, int target) {
    // edge check
    if (A == null || A.length == 0) {
        return -1;
    }
    // binary search
    int left = 0, right = A.length - 1;
    int mid;
    while (left + 1 < right) {
        mid = (left + right) / 2;

        if (A[mid] > target) {
            right = mid;
        } else if (A[mid] == target) {
            return mid;
        } else {
            left = mid;
        }
    }
    // check adjacent
    if (diff(A[left], target) < diff(A[right], target)) {
        return left;
    } else {
        return right;
    }
}

Simple recrusion can be implemented with while loop. Logarithmic time with constant space.