二分查找专题
Binary Search.png
2.Search for a Range
参考程序
public class Solution {
public int[] searchRange(int[] A, int target) {
if (A.length == 0) {
return new int[]{-1, -1};
}
int start, end, mid;
int[] bound = new int[2];
// search for left bound
start = 0;
end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
end = mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[start] == target) {
bound[0] = start;
} else if (A[end] == target) {
bound[0] = end;
} else {
bound[0] = bound[1] = -1;
return bound;
}
// search for right bound
start = 0;
end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
start = mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] == target) {
bound[1] = end;
} else if (A[start] == target) {
bound[1] = start;
} else {
bound[0] = bound[1] = -1;
return bound;
}
return bound;
}
}
// version 1: find the first position >= target
public class Solution {
public int searchInsert(int[] A, int target) {
if (A == null || A.length == 0) {
return 0;
}
int start = 0, end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] == target) {
return mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[start] >= target) {
return start;
} else if (A[end] >= target) {
return end;
} else {
return end + 1;
}
}
}
// version 2: find the last position < target, return +1， 要特判一下target小于所有数组里面的元素
public class Solution {
public int searchInsert(int[] A, int target) {
if (A == null || A.length == 0) {
return 0;
}
int start = 0;
int end = A.length - 1;
int mid;
if (target < A[0]) {
return 0;
}
// find the last number less than target
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
return mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] == target) {
return end;
}
if (A[end] < target) {
return end + 1;
}
if (A[start] == target) {
return start;
}
return start + 1;
}
}
4.Search a 2D Matrix
特征：下一行的数都比该行数大，右边的数比左边的数大
参考程序
// Binary Search Twice 先按照列，用二分法找到在哪一行，然后再用二分法在该行中找到该数
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
if (matrix[0] == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int column = matrix[0].length;
// find the row index, the last number <= target
int start = 0, end = row - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[mid][0] == target) {
return true;
} else if (matrix[mid][0] < target) {
start = mid;
} else {
end = mid;
}
}
if (matrix[end][0] <= target) {
row = end;
} else if (matrix[start][0] <= target) {
row = start;
} else {
return false;
}
// find the column index, the number equal to target
start = 0;
end = column - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[row][mid] == target) {
return true;
} else if (matrix[row][mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (matrix[row][start] == target) {
return true;
} else if (matrix[row][end] == target) {
return true;
}
return false;
}
}
// Binary Search Once
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
if (matrix[0] == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length, column = matrix[0].length;
int start = 0, end = row * column - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
int number = matrix[mid / column][mid % column];
if (number == target) {
return true;
} else if (number < target) {
start = mid;
} else {
end = mid;
}
}
if (matrix[start / column][start % column] == target) {
return true;
} else if (matrix[end / column][end % column] == target) {
return true;
}
return false;
}
}
5.Search a 2D Matrix II
特征：下一行的数都不一定比该行数大，右边的数比左边的数大
Search a 2D Matrix II.png
第二种方法，从左下角或者右上角开始查找，比如左下角的118比他所在的列都大，比他所在的行都小，比如找120的个数，120大于118，那118所在的列可以删除了，列数加1，126大于120，那126所在的行可以删除了，行数减1，123大于120，行数再减1，以此类推，当找到120时，行数减一，列数加1.
参考程序
Search a 2D Matrix II 2.png
6.First Bad Version
参考程序
7.Find Peak Element
参考程序
class Solution {
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
// write your code here
int start = 1, end = A.length-2; // 1.答案在之间，2.不会出界
while(start + 1 < end) {
int mid = (start + end) / 2;
if(A[mid] < A[mid - 1]) {//mid的左边是下降的，那么峰值肯定在它的左边
end = mid;
} else if(A[mid] < A[mid + 1]) {//mid的右边是上升的，那么峰值肯定在它的右边
start = mid;
} else {//mid的左边上升，右边下降，那它很可能是峰值了
end = mid;
}
}
if(A[start] < A[end]) {
return end;
} else {
return start;
}
}
}
8.Search in Rotated Sorted Array
参考程序
Rotated.png
9.Find Minimum in Rotated Sorted Array
参考程序
参考程序2
10.Remove Duplicates from Sorted Array
11.Remove Duplicates from Sorted Array II
12.Median of Two Sorted Arrays
kth number.png
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
int len = A.length + B.length;
if (len % 2 == 1) {
return findKth(A, 0, B, 0, len / 2 + 1);
}
return (
findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)
) / 2.0;
}
// find kth number of two sorted array
public static int findKth(int[] A, int A_start,
int[] B, int B_start,
int k){
//若A数组中的数都删除完了，那直接在B数组中找第K大的数。
//递归终止一般取可变参数的极端条件。
if (A_start >= A.length) {
return B[B_start + k - 1];
}
if (B_start >= B.length) {
return A[A_start + k - 1];
}
if (k == 1) {
return Math.min(A[A_start], B[B_start]);
}
int A_key = A_start + k / 2 - 1 < A.length
? A[A_start + k / 2 - 1]
: Integer.MAX_VALUE;
int B_key = B_start + k / 2 - 1 < B.length
? B[B_start + k / 2 - 1]
: Integer.MAX_VALUE;
//基本原理是把A.B合并成为一个顺序的C数组，删除2/k个数，当A_key < B_key，说明此时A的前K/2个数已经全部放进了C数组中，而B中的第K/2个数还没有放进去，C中还不到K个数，那此时C中的数肯定不满足第K大，A中的前K/2个数可以都删除，所以A的A_start 右移动K/2个位置，此时需要找第 k - k / 2大小的数了。
if (A_key < B_key) {
return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
} else {
return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
}
}
}
13.三步反转法解决以下问题
