Lexi's Leetcode solutions

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

熟悉了二分法的pq终止条件，再做这个题就可厉害了！！先用二分法找左边的7（就算找到了8，就当没看见，因为想找7,8之间的一个数）；再找右边的10。注意：最后如果两个boundry连起来了，说明之间啥也没有，就是没找到8，就全赋成-1.

public int[] searchRange(int[] A, int target) {
  int[] result = new int[2];
  int prevIndex = findPrevIndex(A, 0, A.length - 1, target);
  int nextIndex = findNextIndex(A, 0, A.length - 1, target);
  if (prevIndex + 1 == nextIndex) {
    result[0] = result[1] = -1;
  } else {
    result[0] = prevIndex + 1;
    result[1] = nextIndex - 1;
  }
  return result;
}
private int findPrevIndex(int[] A, int p, int q, int x) {
  if (p > q)
    return q;
  int mid = (p + q) / 2;
  if (A[mid] < x) //abandon left half
    return findPrevIndex(A, mid + 1, q, x);
  else //when A[mid] ==x, treat x as if it's really big because we want to find left boundry
    return findPrevIndex(A, p, mid - 1, x);
}
private int findNextIndex(int[] A, int p, int q, int x) {
  if (p > q)
    return p;
  int mid = (p + q) / 2;
  if (A[mid] <= x)
    return findNextIndex(A, mid + 1, q, x);
  else
    return findNextIndex(A, p, mid - 1, x);
 }