Lexi's Leetcode solutions

[leetcode] Search In Rotated Sorted Array 1&2| 被旋转一次的sorted数组,找x的index

Posted on: October 13, 2013

这个题尽管是CC150上的,理论上很简单,但是想明白(而且用好的方法)很不容易。

1. 数组没有重复

  1. 既然是断开一次的数组,说明A[p] > A[q]。我们从中间一刀划分,想出找sorted那一半,看是否包含x,包含的话就在sorted那一半找;不包含就在broken那一半找。
  2. 这个是根据A[mid]和A[p]来初步划分,平时binary search都是根据A[mid]和x来直接划分。所以一开始做复杂了。这个题按上面说的定义做最好,简单易懂。
  3. 当A[mid] == A[p]的时候,说明mid==p,就左边这一个点,既然已经判断过A[mid] != x了,所以直接找右边就好了。
public int search(int[] A, int target) {
  return find(A, 0, A.length - 1, target);
}
private int find(int[] arr, int p, int q, int x) {
  if (p > q)
    return -1;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
    return mid;
  if (arr[p] < arr[mid]) { // left is ordered, right is broken
    if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
      return find(arr, p, mid - 1, x);
    else // x doesn't belong to left ordered part
      return find(arr, mid + 1, q, x);
  } else if (arr[p] > arr[mid]) {// left is broken, so right is ordered
    if (arr[mid] <= x && x <= arr[q])
      return find(arr, mid + 1, q, x);
    else
      return find(arr, p, mid - 1, x);
  } else { // a[p] == a[mid], directly search right
      return find(arr, mid + 1, q, x);
  }
}

2. 数组有重复数字

  1. 还是从中间一刀划分,想找出sorted那一半,看是否包含x。
  2. 但是当A[p] == A[mid]的时候,不能说明左边就是长度为1的一半了。左边可以是全是repeat,也可以是包含x。
  3. 这时要和A[q]比较,如果A[mid] == A[q],总不能整个数组平了吧。这时候x可以是左边也可以是在右边,必须两边找。
  4. 如果A[mid] != A[q],说明右半部分有起伏,左边的平的这段就不能有起伏了(自己画一下吧)。所以还是找右边。
public boolean search(int[] A, int target) {
  return find(A, 0, A.length - 1, target) >= 0;
}
private int find(int[] arr, int p, int q, int x) {
  if (p > q)
    return -1;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
    return mid;
 
  if (arr[p] < arr[mid]) { //left is ordered, right is broken
    if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
      return find(arr, p, mid - 1, x);
    else //x doesn't belong to left orderd part
      return find(arr, mid + 1, q, x);
  } else if (arr[p] > arr[mid]) {//left is broken, so right is ordered
    if (arr[mid] <= x && x <= arr[q])
      return find(arr, mid + 1, q, x);
    else
      return find(arr, p, mid - 1, x);
  } else { // arr[p] = arr[mid], don't know which side is broken
    if (arr[mid] == arr[q]) {
      int leftResult = find(arr, p, mid - 1, x);
      return leftResult == -1 ? find(arr, mid + 1, q, x) : leftResult;
    } else { //mid is not equals right, so left is all repeats, search right
      return find(arr, mid + 1, q, x);
    }
  }
}
Advertisements

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: