[leetcode] Search In Rotated Sorted Array 1&2| 被旋转一次的sorted数组,找x的index
Posted October 13, 2013
on:这个题尽管是CC150上的,理论上很简单,但是想明白(而且用好的方法)很不容易。
1. 数组没有重复
- 既然是断开一次的数组,说明A[p] > A[q]。我们从中间一刀划分,想出找sorted那一半,看是否包含x,包含的话就在sorted那一半找;不包含就在broken那一半找。
- 这个是根据A[mid]和A[p]来初步划分,平时binary search都是根据A[mid]和x来直接划分。所以一开始做复杂了。这个题按上面说的定义做最好,简单易懂。
- 当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. 数组有重复数字
- 还是从中间一刀划分,想找出sorted那一半,看是否包含x。
- 但是当A[p] == A[mid]的时候,不能说明左边就是长度为1的一半了。左边可以是全是repeat,也可以是包含x。
- 这时要和A[q]比较,如果A[mid] == A[q],总不能整个数组平了吧。这时候x可以是左边也可以是在右边,必须两边找。
- 如果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); } } }
Tags: binarySearch, hard
Leave a Reply