Lexi's Leetcode solutions

[leetcode] Seach for a Range | 二分法找排好序的数组的某个数的起始位置和终止位置

Posted on: August 19, 2013

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);
 }

1 Response to "[leetcode] Seach for a Range | 二分法找排好序的数组的某个数的起始位置和终止位置"

so cute!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: