[关闭]
@xmruibi 2015-02-13T03:43:23.000000Z 字数 7912 阅读 791

Algorithm

This is conclusion for binary search problems.

Some Tips

// notice left < right 还是 left<=right
// 当出现 left/right = middle 时 不可有等号 否则死循环
// 谨慎处理 middle+1|-1 的赋值语句， 严防越过目标位置

1. 给定一个有序（非降序）数组A，求任意一个i使得A[i]等于target，不存在则返回-1

  1.             int search(int a[]): // return index
  2.                     int lo = 0;
  3.                     int hi = a.length()-1;
  4.                     while(lo<=hi):
  5.                         int mi = lo + (hi-lo)/2;
  6.                         if(i == a[mi])
  7.                             return mi;
  8.                         else if(a[mi]<target)
  9.                             hi = mi-1;
  10.                         else
  11.                             lo = mi+1;
  13.                     return -1;

2. 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1

    此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找，如果不存在直接返回-1，如果存在，然后再顺序找到这个等于target值区间的最左位置，这样的话，最坏情况下的复杂度就是O（n）了，没有完全发挥出二分查找的优势。

  1.             int search(int a[]): // return index
  2.                     int lo = 0;
  3.                     int hi = a.length()-1;
  4.                     while(lo<=hi):
  5.                         int mi = lo + (hi-lo)/2;
  6.                         if(i == a[mi])
  7.                             while(a[mi-1] == a[mi])
  8.                                 mi--;
  9.                             return mi;
  10.                         else if(i<a[mi])
  11.                             hi = mi-1;
  12.                         else
  13.                             lo = mi+1;
  15.                     return -1;
  17.         /* 循环过程中，当low大于0时，A[low-1]是小于target的，因为A[mid] < target时， 
  18.         low=mid+1；当high小于n-1时，A[high]是大于等于target的，因为A[mid] >= target时， 
  19.         high = mid；循环结束时，low 等于 high，所以，如果A[low](A[high])等于target， 
  20.         那么low(high)就是target出现的最小位置，否则target在数组中不存在。*/
  21.             int searchFirstPos(int a[]): // return index
  22.                     int lo = 0;
  23.                     int hi = a.length() - 1;
  24.                     while(lo<hi):
  25.                         int mi = lo + (hi-lo)>>1;
  27.                         if(a[mi]>target)
  28.                             lo = mi+1;
  29.                         else
  30.                             hi = mi;
  32.                     if(lo!=target)
  33.                         return -1;
  34.                     else
  35.                         return lo;

3. 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1

  1.             int searchLastPos(int a[]): // return index
  2.                     int lo = 0;
  3.                     int hi = a.length() - 1;
  4.                     while(lo<hi):
  5.             /*  这里中间位置的计算就不能用low+((high-low)>>1)了，因为当low+1等于high 
  6.             且A[low] <= target时，会死循环；所以这里要使用low+((high-low+1)>>1)， 
  7.             这样能够保证循环会正常结束。*/  
  8.                         int mi = lo + (hi-lo+1)>>1;
  10.                         if(a[mi]>target)
  11.                             hi = mi-1;                          
  12.                         else
  13.                             lo = mi;
  15.                     if(hi!=target)
  16.                         return -1;
  17.                     else
  18.                         return hi;

4. 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]小于target，不存在则返回-1

  1.             int searchLastLessThan(int a[]):
  2.                     int lo = 0;
  3.                     int hi = a.length() - 1;
  4.                     while(lo<hi):
  5.                             int mi = lo + (hi-lo+1)>>1;
  6.                             if(a[mi]<target)
  7.                                 lo = mi;
  8.                             else
  9.                                 hi = mi - 1;
  11.                     return a[lo]<target?lo:-1;

5. 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]大于target，不存在则返回-1

  1.             int searchFirstGreaterThan(int a[]):
  2.                     int lo = 0;
  3.                     int hi = a.length() - 1;
  4.                     while(lo<hi):
  5.                             int mi = lo + (hi-lo)>>1;
  6.                             if(a[mi]> target)
  7.                                 hi = mi;
  8.                             else
  9.                                 lo = mi + 1;
  11.                     return a[hi]<target?hi:-1;

6. 给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数。

  1.             int count(int A[], int n, int target):
  2.                     int firstPos = searchFirstPos(A, n, target); // 第一次出现位置  
  3.                     if(firstPos == -1)  
  4.                         return 0;  
  5.                     int lastPos = searchLastPos(A, n, target);  // 最后一次出现位置  
  6.                     return lastPos-firstPos+1;  // 出现次数
  8. 6.* Search for a Range -- LeetCode: similar with the aforementioned solution
  10.             // idea is find the first index of target and 
  11.             // the left element of the first element larger than target
  13.             searchRange(int[] A, int target): 
  15.                 int  start = helper(A, target);
  16.                 if (start == A.length || A[start] != target)
  17.                     return new int[]{-1, -1};
  19.                 int end = helper(A,target+1)-1;
  23.             int helper(int a[], int lo, int hi):
  24.                 while(lo<hi):
  25.                     int mi = lo + (hi - lo)>>1;
  27.                     //low <= mid < high
  28.                     if(a[mi]>target)
  29.                         lo = mi+1;
  30.                     else
  31.                         hi = mi;
  33.                     return lo;

7. （Leetcode: Search Insert Position）给定一个有序（非降序）数组A，若target在数组中出现，返回位置，若不存在，返回它应该插入的位置。

  1.             int search(int a[]): // return index
  2.                     int lo = 0;
  3.                     int hi = a.length()-1;
  4.                     while(lo<hi):
  5.                         int mi = lo + (hi-lo)/2;
  7.                         if(a[mi]>=target)
  8.                             hi = mi;
  9.                         else
  10.                             lo = mi+1;
  12.                     return hi;

8. 给定一个有序（非降序）数组A，可含有重复元素，求绝对值最小的元素的位置

    //找第一个大于等于0的位置，然后和前一个元素的绝对值比较，返回绝对值较小的元素的位置。

  1.             int search(int a[]): // return index
  2.                     int lo = 0;
  3.                     int hi = a.length()-1;
  4.                     while(lo<hi):
  5.                         int mi = lo + (hi-lo)>>1;
  6.                         if(a[mi]>=0)
  7.                             hi = mi;
  8.                         else
  9.                             lo = mi+1;
  11.             /* 循环结束时，如果low != n-1，A[low] >= 0，如果low>0，A[low-1] < 0 */  
  12.                         if(low > 0 && abs(A[low-1]) < abs(A[low]))  
  13.                             return low-1;  
  14.                         else  
  15.                             return low;

9. 给定一个有序（非降序）数组A和一个有序（非降序）数组B，可含有重复元素，求两个数组合并结果中的中位数 (following solution (A.length+ B.length)/2))

Follow Up : 给定一个有序（非降序）数组A和一个有序（非降序）数组B，可含有重复元素，求两个数组合并结果中的第k(k>=0)个数字。
            // A.length < B.length otherwise change A,B
            // keep A[lenB/2] <= B[lenB/2] otherwise change A,B
            // Arrays.copyOfRange(src, 0, 2)

  1.                 private int helper(int A[], int B[], int i, int i2, int j, int j2, int k){  
  2.                     int m = i2-i+1;  
  3.                     int n = j2-j+1;  
  4.                     if(m>n)  
  5.                         return helper(B,A,j,j2,i,i2,k);  
  7.                     if(m==0)  // A is null
  8.                         return B[j+k-1];  
  9.                     if(k==1)  // k == 1 means the minimal number of two arrays
  10.                         return Math.min(A[i],B[j]);  
  12.                     int posA = Math.min(k/2,m);  //!!
  13.                     int posB = k-posA;  //!!
  15.                     if(A[i+posA-1]==B[j+posB-1])  
  16.                         return A[i+posA-1];  
  17.                     else if(A[i+posA-1]<B[j+posB-1])  // 取 A右[i+posA,i2] B左 j,j+posB-1
  18.                         return helper(A,B,i+posA,i2,j,j+posB-1,k-posA);  
  19.                     else  
  20.                         return helper(A,B,i,i+posA-1,j+posB,j2,k-posB);  
  21.                 }

10. Binary Search and Mathematical Problem:

    Sqrt:
    ONLY VALID WHEN THE RETURN VALUE IS INTEGER!

  1.                 int sqrt(int x):
  2.                         if(x < 0)
  3.                             return -1;
  4.                         if(x == 0)
  5.                             return 0;
  6.                         int l = 1;
  7.                         int r = x>>1 +1;
  9.                         while(l<r):
  10.                             int m = l+(r-l)>>1;
  12.                             if(x/m=>m&&m+1>x/m+1)
  13.                                 return m;
  14.                             else if(x/m<m):
  15.                                 r = m-1;
  16.                             else
  17.                                 l = m+1;
  19.                         return 0;
    Pow:

  1.                 // considering with divide and conquer 
  2.                 double pow(int x, int n):
  3.                         if(n==0)
  4.                             return 1.0;
  5.                         double half = pow(x,n/2);
  6.                         if(n%2==0)
  7.                             return half*half;
  8.                         else:
  9.                             if(n%2>0): // n>0
  10.                                 return (half*half)*x;
  11.                             else: // n<0
  12.                                 return (half*half)/x;
    Division:

  1.                 int divide(int dividend, int divisor):
  3.                         int res = 0;
  5.                         // several corner cases: 
  6.                         if(divisor == 0) // illegal input
  7.                             return Integer.MAX_VALUE;
  9.                         else if (divisor == 1)
  10.                             return dividend;
  12.                         else if(dividend == Integer.MIN_VALUE):
  13.                             if (divisor == -1) // ensure the result in the range of 2^31-1 ~ -2^31
  14.                                 return (dividend == Integer.MIN_VALUE) ? Integer.MAX_VALUE : -dividend;
  16.                             dividend += Math.abs(divisor);  
  17.                             res++;
  19.                          if(divisor == Integer.MIN_VALUE)
  20.                             return res;
  23.                         boolean isNeg = (dividend^divisor)>>>31 == 1;
  25.                         dividend = Math.abs(dividend);  
  26.                         divisor = Math.abs(divisor);  
  28.                         // 位操作法。。。
  29.                         int digit = 0; //  
  30.                         while(divisor <= (dividend>>1)):   // 除数 小于 被除数的二分一
  31.                             divisor <<= 1;  // 除数*2
  32.                             digit++;  
  35.                         while(digit>=0): 
  36.                             if(dividend>=divisor):
  37.                                 res += 1<<digit;  // 1 左移 digit位 2^digital 
  38.                                 dividend -= divisor;  
  40.                             divisor >>= 1;  
  41.                             digit--;  
  43.                         return isNeg?-res:res; 
  45.                         // 二分法???

11. Find Peak Element

    如果中间元素大于其相邻后续元素，则中间元素左侧（包含该中间元素）必包含一个局部最大值。
    如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。

  1.                 int findPeak(int[] a):
  2.                         int l = 0;
  3.                         int r = a.length - 1;
  4.                         while(l<=r):
  5.                             int mi = l + (r-l)/2;
  6.                             if(l ==r)
  7.                                 return l;
  8.                             if(a[mi]<a[mi+1])
  9.                                 l = mi+1;
  10.                             else
  11.                                 r = mi;
  13.                         return 0;

12. Search a 2D Matrix

    因为矩阵是行有序并且列有序，查找只需要先按行查找，定位出在哪一行之后再进行列查找即可，所以就是进行两次二分查找。
    时间复杂度是O(logm+logn)，空间上只需两个辅助变量，因而是O(1).

  1.                 boolean searchMatrix(int[][] matrix, int target): 
  2.                         if(matrix == null || matrix.length==0 || matrix[0].length==0)  
  3.                             return false;
  5.                         int row = 0;
  6.                         // find row
  7.                         int l = 0;
  8.                         int r = matrix.length - 1;
  9.                         while(l<=r):
  10.                             int m = l + (r - l)>>1;
  11.                             if(matrix[m][0]==target)
  12.                                 return true;
  14.                             if(matrix[m][0]>target)
  15.                                 r = m-1;
  16.                             else
  17.                                 l = m+1;
  19.                         row = r;
  20.                         if(row<0)  
  21.                             return false;  
  23.                         l = 0;
  24.                         r = matrix[0].length - 1;
  25.                         while(l<r):
  26.                             int m = l + (r - l)>>1;
  27.                             if(matrix[row][m]==target)
  28.                                 return true;
  29.                             if(matrix[row][m]<target)
  30.                                 r = m - 1;
  31.                             else
  32.                                 l = m + 1;
  34.                         return false;

13.Rotated Sorted Array 系列！

如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2


我们先比较中间元素是否是目标值，如果是返回位置。如果不是，我们就应该想办法将搜索区间减少一半。因为存在旋转变化，所以我们要多做一些判断。
我们知道因为只有一次旋转变化，所以中间元素两边的子数组肯定有一个是有序的，那么我们可以判断target是不是在这个有序的子数组中，
从而决定是搜索这个子数组还是搜索另一个子数组。
13.1. Search in Rotated Sorted Array
    You should assume no duplicate exists!!
    (1) 如果target==A[m]，那么m就是我们要的结果，直接返回；
    (2) 如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，
        如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
    (3) 如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。

    时间复杂度是O(logn)，空间复杂度是O(1)。

  1.                 int search(int[] A, int target)：
  2.                         int l = 0;
  3.                         int r = A.length;
  5.                         while(l<r):
  6.                             int m = l + (r-l)>>1;
  7.                             if(A[m]==target)
  8.                                 return m;   
  10.                             if(A[m]>=A[l]): // l ~ m 升序
  12.                                 if(A[m]>target&&A[l]<=target) //target 不能小于l
  13.                                     r = m-1;
  14.                                 else
  15.                                     l = m+1;
  17.                             else:
  19.                                 if(A[m]<target&&A[r]>=target) // target 不能大于r
  20.                                     l = m+1;
  21.                                 else
  22.                                     r = m-1;
  24.                         return -1;
13.2. Search in Rotated Sorted Array II
    Duplicate is allowed!
    但我们会遇到中间和边缘相等的情况，我们就丢失了哪边有序的信息，因为哪边都有可能是有序的结果。
    假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，
    这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。
    解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。
    所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）
    就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。

  1.                         boolean search(int[] A, int target)：
  2.                         int l = 0;
  3.                         int r = A.length;
  5.                         while(l<r):
  6.                             int m = l + (r-l)>>1;
  7.                             if(A[m]==target)
  8.                                 return true;    
  10.                             if(A[m]>A[l]): // l ~ m 升序
  12.                                 if(A[m]>target&&A[l]<=target) //target 不能小于l
  13.                                     r = m-1;
  14.                                 else
  15.                                     l = m+1;
  17.                             else if(A[m]<A[l]): // m ~ r 升序
  19.                                 if(A[m]<target&&A[r]>=target) // target 不能大于r
  20.                                     l = m+1;
  21.                                 else
  22.                                     r = m-1;
  24.                             else // A[m] == A[l]
  25.                                 l++;  // this is the solution to deal with duplicated elements
  27.                         return false;
13.3. 一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求最小值所在位置
    假如翻转后的数组以第 x 个结点分为两部分 A[0..x] 和 A[x+1..n]。
    则 A[0..x] 这一段是有序递增的， A[x+1..m] 这一段也是有序递增的。
    并且因为原数组是有序递增的，A[0..x] 中所有数都会大于 A[x+1..n] 中的任何数。
    所以我们其实就是需要找到结点 A[x+1]，这个结点的值就是最小值。

    No duplicated:
        Solution One:

  1.                 int searchMin(int[] A):
  2.                         if(A.length == 0)
  3.                             return o;
  4.                         int l = 0, r = A.length - 1;
  5.                         while(l<r):
  6.                             int m = l+ (r-l)>>1;
  7.                             if(A[l]>A[r]):
  8.                                 if(A[l]<=A[m])
  9.                                     l = m+1;
  10.                                 else
  11.                                     r = m;
  12.                             else
  13.                                 return A[left];
  15.                         return A[left];
    Has duplicated:

  1.                 int searchMin(int[] A):
  2.                         int l = 0;
  3.                         int r = num.length-1;
  4.                         int min = Integer.MAX_VALUE;
  5.                         while(l < r-1):
  6.                             int m = l+ (r-l)>>1;
  7.                             if(A[m]>A[l]):
  8.                                 min = Math.min(min,A[l]);
  9.                                 l = m + 1;
  10.                             else if(A[m]<A[l]):
  11.                                 min = Math.min(min,A[m]);                               
  12.                                 r = m - 1;
  13.                             else
  14.                                 l++;
  16.                         min = Math.min(Math.min(min, A[l]), A[r]);
  17.                         return min;
13.4. 一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求第k(k > 0)小元素
  1.                 int searchKthInRotatedArray(int A[], int n, int k):
  2.                         int posMin = searchMinInRotatedArray(A, n);  
  3.                         return (posMin+k-1)%n;
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注