Cracking Coding Interview - 10.3 Search in Rotated Array

2019-08-28 2 分钟阅读 ARTS-A

Search in Rotated Array: Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

EXAMPLE

1
2

lnput: find 5 in {l5, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}
Output: 8 (the index of 5 in the array)

Hints: #298, #310

解法1

你可以认为在一个循环有序数组里查找。

把这个数组中间切一刀，那么会发现左右两边至少会有一边是有序的（头 < 尾）。我们在有序的里面二分查找，在无需的那么在另一边里再切一刀找。

步骤：

  1. 把数组中间切一刀，会得到L、R两个数组
  2. 如果某个数组的头 < 尾，说明它是有序的，启用二分查找
  3. 如果某个数组的头 >= 尾，说明它是无序的，对它重复1-3步
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public int search(int[] a, int n, int start, int end) {
  if (start > end) {
    return -1;
  }
  if (a[start] >= a[end] && end - start > 0) {
    // 本段不是有序的
    int mid = (start + end) / 2;
    int result = search(a, n, start, mid);
    if (result != -1) {
      return result;
    }
    return search(a, n, mid + 1, end);
  }
  
  if (a[start] <= n && n <= a[end]) {
    // 本段是有序的
    return binarySearch(a, n, start, end);    
  }
  // 本段有序但是所求值不在我的范围内
  return -1;
}

private int binarySearch(int[] a, int n, int start, int end) {
  if (start > end) {
    return -1;
  }
  int mid = (start + end) / 2;
  if (a[mid] == n) {
    return mid;
  } else if (a[mid] < n) {
    return binarySearch(a, n, mid + 1, end);
  } else {
    return binarySearch(a, n, statt, mid - 1);
  }
}

时间复杂度：

  • 如果本来就是有序的，复杂度是O(log n)，和二分一样
  • 如果全部都是重复元素，复杂度O(n)，比如在[3,3,3,3]里找2，那么最终会对4个3做二分。
Cracking Coding Interview - 10.2 Group Anagrams
Cracking Coding Interview - 10.4 Sorted Search, No Size

版权

CC BY-NC-ND 4.0

相关文章

评论