Star

[LintCode] Closest number in sorted array

Posted on | In |

Question

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.

Explanation

被面到了这道题！先排个序，接着二分查找。注意最后选择start还是选择end。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void search(int[] array, int k) {
  Arrays.sort(array);
  int start = 0;
  int end = arrays.length;
  while(start+1 < end) {
    int mid = start + (end - start)/2;
    if (array[mid] == k) return mid;
    if (array[mid] > k) {
      start = mid;
    } else {
      end = mid;
    }
  }
  if (k <= array[start]) return start;
  if (k >= array[end]) return end;
  if (k - array[start] > array[end] - k) {
    return end;
  } else {
    return start;
  }
}