# Closest in Sorted Array

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

**Assumptions**

* There can be duplicate elements in the array, and we can return any of the indices with same value.

**Examples**

* A = {1, 2, 3}, T = 2, return 1
* A = {1, 4, 6}, T = 3, return 1
* A = {1, 4, 6}, T = 5, return 1 or 2
* A = {1, 3, 3, 4}, T = 2, return 0 or 1 or 2

**Corner Cases**

* What if A is null or A is of zero length? We should return -1 in this case.

**High Level:**

left++ right-- until left is first element greater than target

check for closer between left and left - 1

**Mistake Made:**

When target out of bounds, edge case need to be handled to avoid IndexOutOfBounds error

```
public class Solution {
  public int closest(int[] array, int target) {
    if (array.length == 0) return -1;
    // Move right to first element N > target
    // check between N and N - 1 for closer
    int left = 0;
    int right = array.length - 1;
    while (left <= right){
      int mid = left + (right - left) / 2;
      if (array[mid] == target) return mid;
      else if (array[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
    if (left < 1) return 0;
    if (left > array.length - 1) return array.length - 1;
    //left should end just greater than mid
    //check between left and left - 1
    if (Math.abs(array[left] - target) < Math.abs(array[left - 1] - target)) return left;
    else return right;
  }
}
```

Time Complexity: O(logN)&#x20;

Space Complexity: O(1)