二分法：通过O(1)的时间，把规模为n的问题变为n/2。T(n) = T(n/2) + O(1) = O(logn)。
基本操作：把长度为n的数组，分成前区间和后区间。设置start和end下标。int start = 0, end = nums.length - 1。循环结束条件为start + 1 < end ，即相邻时结束循环，所以最后需判断start和end中哪个是目标值。指针变化为start = mid，取后半区间；end = mid，取前半区间。
经典二分搜索：1. First postion of target：找到目标后取前半区间继续搜索
2. Last position of target: 找到目标后取后半区间继续搜索
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
end = mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
public int lastPosition(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
start = mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[end] == target) {
return end;
}
if (nums[start] == target) {
return start;
}
return -1;
}
【lintcode459】排序数组中最接近元素。
public int closestNumber(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
int index = firstIndex(A, target);
if (index == 0) {
return 0;
}
if (index == A.length) {
return A.length - 1;
}
if (target - A[index - 1] < A[index] - target) {
return index - 1;
}
return index;
}
private int firstIndex(int[] A, int target) {
int start = 0, end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < target) {
start = mid;
} else if (A[mid] > target) {
end = mid;
} else {
end = mid;
}
}
if (A[start] >= target) {
return start;
}
if (A[end] >= target) {
return end;
}
return A.length;
}
【lintcode28】搜索二维矩阵
思路：先寻找相应行数，可利用二分法，本人使用直接查找法，只是复杂度较高。需要注意的是要用某行末位数和target比较，而不是行数首位数。
public boolean searchMatrix(int[][] matrix, int target) {
// write your code here
if(matrix == null || matrix.length == 0 ||matrix[0].length == 0){
return false;
}
int start = 0;
int row = 0;
int column = matrix[0].length - 1;
while(matrix[row][column]<target && row < matrix.length-1){
row ++;
}
int end = matrix[0].length-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;
}
if(matrix[row][end] == target){
return true;
}
return false;
}
O(logn+logm)参考答案
// 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 {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
// write your code here
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; int start = 0, end = row * column - 1;
while(start <= end){
int mid = start + (end - start) / 2;
int number = matrix[mid / column][mid % column];
if(number == target){
return true;
}else if(number > target){
end = mid - 1;
}else{
start = mid + 1;
}
} return false; }
}