Lexi's Leetcode solutions

Posts Tagged ‘binarySearch

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

这个好像两年前在纽约就做过,到今天才好好分析了一遍。Leetcode上面的这篇分析特别特别好,看过一遍顺便还练习算时间复杂度了。总之两个比较好的解法:

1. O(n)的linear解法:

因为二维矩阵是行列都sort好的,所以最上面一行和最右边一列正好形成了一个sort好的递增数列。取右上角这个A[i][j],它左边的全<x, 它下边的全>x,所以每次可以删掉一行/列。这样每次往下/往左走一步,最后要是走到左下角了还没找到,那走的最多步数是m + n步。所以时间是O(m + n)。

public boolean searchMatrixLinear(int[][] matrix, int target) {
  int i = 0, j = matrix[0].length - 1;
  while (i < matrix.length && j >= 0) {
    if (matrix[i][j] == target)
      return true;
    else if (matrix[i][j] > target) // eliminate col, go left
      j--;
    else
      i++; // eliminate row, go down
  }
  return false;
}

2. O(logm * logn)的更快的解法:

每次取中间一列,然后在这一列里面binary search,要是没找到,最后会找到(j1, j2)这样的两个位置,A[i][j1] < x && A[i][j2]。说明(i, j1)左上的全<x,(i, j 2)右下的全>x,说明x肯定不在这两块里面,就可以eliminate掉了。在剩下的两块里面各自找x,然后返回||。

这个时间复杂度为什么是O(logm * logn)?每次删掉行数的一半,是logm,在每个check的row里面做一次binary search是logn。

public boolean searchMatrixFastest(int[][] matrix, int target) {
  return searchBinary(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);
}
private boolean searchBinary(int[][] matrix, int i1, int i2, int j1, int j2, int x) {
  if (i1 > i2 || j1 > j2)
    return false;
  int midRow = (i1 + i2) / 2; 
  int midCol = searchInRow(matrix, midRow, j1, j2, x); 
  if (midCol == -10) //用-10不用-1因为可能没找到但是q=-1
    return true;
  return searchBinary(matrix, i1, midRow - 1, midCol + 1, j2, x) || searchBinary(matrix, midRow + 1, i2, j1, midCol, x);
}
private int searchInRow(int[][] matrix, int i, int p, int q, int x) {
  while (p <= q) {
    int mid = (p + q) / 2;
    if (matrix[i][mid] == x)
      return -10;
    else if (matrix[i][mid] > x) // go up
      q = mid - 1;
    else
      p = mid + 1;
  }
  return q;
}

 

 

这题真是做了挺久,尼玛还是二分法不熟悉。。怎么终止还是想了很久。

二分法永远是(p, mid – 1)和(mid + 1, q), 不要想什么(p, mid)之类的,那样范围永远没法缩小,最后肯定死循环。

二分的模板终止条件永远是p > q,不要去想p == q + 1, p == q这些,这些都可以经过下一次recurse再分解成p > q的形式。

最后p > q说明没找到,比如foo(5, 4),即那么x应该是在4,5之间,这个时候p的值是5,q的值是4,说明小的那个是q,大的那个是p。所以二分法找x应该在的index那题返回p(返回较大的),这题应该返回q(返回较小的)。别去考虑p==q之类的的情况,那种再走一遍就会又形成p > q。若是找到了,更会在mid==x这个catch里直接接住,不用在终止条件处考虑。

还有一个要注意的地方:代码中间有mid * mid这种式子,这个就很可能overflow,所以要在出现这个之前接住overflow的情况。因为整数的乘法可能导致溢出,而溢出的监测和整数加法直接判断是否小于0是不同的(整数加法溢出时和会<0因为第一位bit被从0顶到1了),因为整数的乘法有可能多次溢出,当奇书次溢出时是负数,当偶数次溢出时时整数。网上看的巧妙的解决办法是干脆不要乘,而是用x/mid和mid比较。

public int sqrt(int x) {
    return sqrt(x, 1, x);
}
private int sqrt(int x, int p, int q) {
    if (p > q)
        return q;
    int mid = (p + q) / 2;
    if (x / mid == mid)
        return mid;
    else if (x / mid < mid )
        return sqrt(x, p, mid - 1);
    else
        return sqrt(x, mid + 1, q);
}

比如{1, 2, 4, 5},3的supposed index就应该是2(把4的位置顶替了)。

facts:

  • because in the end, when p’s next is q, the mid will == p, and new left section will be [q, p](q is mid – 1 and p stays); new right section will be [q, p] (p is mid + 1 and q stays), which ever, we want to return the p because we didn’t find x!
  •  is there a possibility where in the end p’s next is not q? like p q somehow points to the same element, then it’s the same, we want to return p.
  • that’s all the possible combinations. There’s no way [p, somethinglese, q] in the end, that will always transform to scenario 1 or scenario 2.
int findSupposedIndex(int[] arr, int x, int p, int q) {
  if (p > q)
    return p;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
      return mid;
  else if (arr[mid] > x)
      return findSupposedIndex(arr, x, p, mid - 1);
  else
      return findSupposedIndex(arr, x, mid + 1, q);

private int findKth(int[] A, int[] B, int k) {
if (A.length == 0 && B.length == 0)
return 0;
return findKth(A, B, 0, 0, k);
}

private int findKth(int[] A, int[] B, int i, int j, int k) {
if (A.length – i > B.length – j)
return findKth(B, A, j, i, k);
if (i == A.length)
return B[j – 1 + k]; // the kth starting from j
if (k == 1) //when trying to find the first, just return the smaller head
return Math.min(A[i], B[j]);
int m1, m2; // section size
if (A.length – i < k / 2) { // A’s left over (start from A[i] to A[last]) can’t slice a size k/2 section
m1 = A.length – i;
} else {
m1 = k / 2;
}
m2 = k – m1;
int i1 = i + m1 – 1; // the pivot’s index in A
int j1 = j + m2 – 1;
if (A[i1] < B[j1]) // abandon A’s left section including A[i1]
return findKth(A, B, i1 + 1, j, k – m1);
else if (A[i1] > B[j1]) {// abandon B’s left section including B[j1],
return findKth(A, B, i, j1 + 1, k – m2);
} else {
return A[i1];
}
}

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