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

Posted by: lexigrey on: October 13, 2013

• In: leetcode
• Leave a Comment

这个题尽管是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

Tags: binarySearch, hard