算法之美——二分法
作者: 康凯森
日期: 2016-06-16
分类: 算法
- 什么时候用二分？
- 二分法模板的四点要素
- 二分法关键
- classical-binary-search
- first-position-of-target
- last-position-of-target
- search-insert-position
- search-a-2d-matrix
- search-a-2d-matrix-ii
- search-in-a-big-sorted-array
- find-minimum-in-rotated-sorted-array
- find-minimum-in-rotated-sorted-array-ii
- find-peak-element
- first-bad-version
- search-in-rotated-sorted-array
- search-for-a-range
- total-occurrence-of-target
- closest-number-in-sorted-array
- k-closest-numbers-in-sorted-array
- wood-cut
- sqrtx
- 参考资料
什么时候用二分？
O(logn)的时间复杂度- 有序数组
二分法模板的四点要素
- start + 1 < end
- start + (end - start) / 2
- A[mid] ==, <, >
- A[start] A[end] ? target
二分法关键
- 头尾指针，取中点，判断往哪儿走
- 寻找满足某个条件第一个或是最后一个位置
- 保留剩下来一定有解的那一半
classical-binary-search
在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1
public class Solution {
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
public int findPosition(int[] A, int target) {
// Write your code here
if (A == null || A.length == 0){
return -1;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == A[mid]) {
end = mid;
} else if (target > A[mid]) {
start = mid;
} else {
end = mid;
}
}
if (target == A[start]) {
return start;
}
if (target == A[end]) {
return end;
}
return -1;
}
}
first-position-of-target
在有序数组中查找元素，返回第一个位置。
class Solution {
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
public int binarySearch(int[] nums, int target) {
//write your code here
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == nums[mid]) {
end = mid;
} else if (target > nums[mid]) {
start = mid;
} else {
end = mid;
}
}
if (target == nums[start]) {
return start;
}
if (target == nums[end]) {
return end;
}
return -1;
}
}
last-position-of-target
给一个升序数组，找到target最后一次出现的位置，如果没出现过返回-1
public class Solution {
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
public int lastPosition(int[] A, int target) {
// Write your code here
if (A == null || A.length == 0){
return -1;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == A[mid]) {
start = mid;
} else if (target > A[mid]) {
start = mid;
} else {
end = mid;
}
}
if (target == A[end]) {
return end;
}
if (target == A[start]) {
return start;
}
return -1;
}
}
search-insert-position
搜索插入位置
public class Solution {
/**
* param A : an integer sorted array
* param target : an integer to be inserted
* return : an integer
*/
// find the first position >= target
public int searchInsert(int[] A, int target) {
// write your code here
if (A == null || A.length == 0){
return 0;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (target == A[mid]) {
return mid;
} else if (target < A[mid]){
end = mid;
} else {
start = mid;
}
}
if (target <= A[start]) {
return start;
} else if (target <= A[end]) {
return end;
} else {
return end + 1;
}
}
}
search-a-2d-matrix
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
- 每行中的整数从左到右是排序的。
- 每行的第一个数大于上一行的最后一个整数。
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
boolean found = false;
if (matrix == null || matrix.length == 0){
return found;
}
int row = matrix.length;
int column = matrix[row - 1].length - 1;
int i = 0;
while (i < row && column >= 0){
if (target == matrix[i][column]) {
return found = true;
} else if (target < matrix[i][column]) {
column --;
} else {
i ++;
}
}
return found;
}
}
search-a-2d-matrix-ii
写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
这个矩阵具有以下特性：
- 每行中的整数从左到右是排序的。
- 每一列的整数从上到下是排序的。
- 在每一行或每一列中没有重复的整数。
public class Solution {
/**
* @param matrix: A list of lists of integers
* @param: A number you want to search in the matrix
* @return: An integer indicate the occurrence of target in the given matrix
*/
public int searchMatrix(int[][] matrix, int target) {
// write your code here
if (matrix == null || matrix.length == 0){
return 0;
}
int count = 0;
int row = matrix.length;
int column = matrix[row - 1].length;
int i = 0;
while (i < row && column > 0){
if (matrix[i][column - 1] == target){
count ++;
column --;
}
else if (matrix[i][column - 1] > target)
column --;
else
i ++;
}
return count;
}
}
search-in-a-big-sorted-array
给一个按照升序排序的正整数数组。这个数组很大以至于你只能通过固定的接口 ArrayReader.get(k) 来访问第k个数。并且你也没有办法得知这个数组有多大。找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。
如果找不到target，返回-1。
/**
* Definition of ArrayReader:
*
* class ArrayReader {
* // get the number at index, return -1 if not exists.
* public int get(int index);
* }
*/
public class Solution {
/**
* @param reader: An instance of ArrayReader.
* @param target: An integer
* @return : An integer which is the index of the target number
*/
public int searchBigSortedArray(ArrayReader reader, int target) {
// write your code here
int index = 1;
while (reader.get(index - 1) < target && reader.get(index - 1) != -1) {
index = index * 2;
}
int start = 0;
int end = index - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == reader.get(mid)) {
end = mid;
} else if (target > reader.get(mid)) {
start = mid;
} else {
end = mid;
}
}
if (target == reader.get(start)) {
return start;
}
if (target == reader.get(end)) {
return end;
}
return -1;
}
}
find-minimum-in-rotated-sorted-array
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
你可以假设数组中不存在重复的元素。
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] num) {
int start = 0;
int end = num.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (num[mid] >= num[end]) {
start = mid;
} else {
end = mid;
}
}
if (num[start] < num[end]) {
return num[start];
} else {
return num[end];
}
}
}
find-minimum-in-rotated-sorted-array-ii
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
数组中可能存在重复的元素。
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] num) {
int start = 0;
int end = num.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (num[start] == num[end] && num[start] == num[mid])
return findInOrder(num); //退化到顺序查找
else if (num[mid] >= num[end]) {
start = mid;
} else {
end = mid;
}
}
if (num[start] < num[end]) {
return num[start];
} else {
return num[end];
}
}
private int findInOrder(int[] num) {
int min = num[0];
for (int i = 1; i < num.length; i++) {
if (num[i] < min)
min = num[i];
}
return min;
}
}
find-peak-element
你给出一个整数数组(size为n)，其具有以下特点：
相邻位置的数字是不同的
A[0] < A[1] 并且 A[n - 2] > A[n - 1]
假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。
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; // 答案在之间
while(start + 1 < end) {
int mid = start + (end - start) / 2;
if(A[mid] < A[mid - 1]) {
end = mid;
} else if(A[mid] < A[mid + 1]) {
start = mid;
} else {
end = mid;
// start = mid; 不影响结果
}
}
if(A[start] < A[end]) {
return end;
} else {
return start;
}
}
}
first-bad-version
代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。
/**
* public class VersionControl {
* public static boolean isBadVersion(int k);
* }
* you can use VersionControl.isBadVersion(k) to judge whether
* the kth code version is bad or not.
*/
class Solution {
/**
* @param n: An integers.
* @return: An integer which is the first bad version.
*/
public int findFirstBadVersion(int n) {
int start = 1;
int end = n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (VersionControl.isBadVersion(mid)) {
end = mid;
} else {
start = mid;
}
}
if (VersionControl.isBadVersion(start)) {
return start;
}
return end;
}
}
search-in-rotated-sorted-array
假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。
你可以假设数组中不存在重复的元素。
public class Solution {
public int search(int[] A, int target) {
if (A == null || A.length == 0)
return -1;
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] == target) {
return mid;
}
if (A[start] < A[mid]) {
// situation 1, red line
if (A[start] <= target && target <= A[mid]) {
end = mid;
} else {
start = mid;
}
} else {
// situation 2, green line
if (A[mid] <= target && target <= A[end]) {
start = mid;
} else {
end = mid;
}
}
}
if (A[start] == target) {
return start;
}
if (A[end] == target) {
return end;
}
return -1;
}
}
search-for-a-range
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回[-1, -1]
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;
}
}
total-occurrence-of-target
给一个升序的数组，以及一个target，找到它在数组中出现的次数。
public class Solution {
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
public int totalOccurrence(int[] A, int target) {
// Write your code here
if (A == null || A.length == 0) {
return 0;
}
int start, end, mid;
int first = 0;
int last = 0;
// search for first
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) {
first = start;
} else if (A[end] == target) {
first = end;
} else {
return 0;
}
// search for last
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) {
last = end;
} else if (A[start] == target) {
last = start;
} else {
return 0;
}
return (last - first + 1);
}
}
closest-number-in-sorted-array
在一个排好序的数组 A 中找到 i 使得 A[i] 最接近 target
public class Solution {
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
public int closestNumber(int[] A, int target) {
// Write your code here
if (A == null || A.length == 0){
return -1;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == A[mid]) {
end = mid;
} else if (target > A[mid]) {
start = mid;
} else {
end = mid;
}
}
if (target - A[start] <= A[end] - target) {
return start;
} else {
return end;
}
}
}
k-closest-numbers-in-sorted-array
给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。
public class Solution {
/**
* @param A an integer array
* @param target an integer
* @param k a non-negative integer
* @return an integer array
*/
public int[] kClosestNumbers(int[] A, int target, int k) {
// Write your code here
int start = 0;
int end = A.length - 1;
int[] result = new int[k];
int length = 0;
if (A == null || A.length < k){
return result;
}
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == A[mid]) {
end = mid;
} else if (target > A[mid]) {
start = mid;
} else {
end = mid;
}
}
for (; length < k && start >= 0 && end < A.length; length++){
if (target - A[start] <= A[end] - target) {
result[length] = A[start];
start--;
} else {
result[length] = A[end];
end++;
}
}
for (; length < k; length++) {
if (start < 0) {
result[length] = A[end];
end++;
} else if (end > A.length - 1) {
result[length] = A[start];
start--;
}
}
return result;
}
}
wood-cut
有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
public class Solution {
/**
*@param L: Given n pieces of wood with length L[i]
*@param k: An integer
*return: The maximum length of the small pieces.
*/
public int woodCut(int[] L, int k) {
// write your code here
if (L == null || L.length == 0 || k < 0) {
return 0;
}
if (L.length == 1) {
return L[0] / k;
}
Arrays.sort(L);
int start = 0;
int end = L[L.length - 1];
int mid = 0;
int max = 0;
while (start + 1 < end) {
mid = start + (end - start) / 2;
int count = 0;
for (int i : L) {
count += i / mid;
}
if (count < k) {
end = mid;
} else {
start = mid;
max = mid;
}
}
return max;
}
}
sqrtx
求一个数的平方根。
public class Solution {
public int sqrt(int x) {
long lo = 0;
long hi = x;
while (hi >= lo) {
long mid = lo+(hi-lo)/2;
if (x < mid * mid) {
hi = mid-1; // not hi = mid
} else {
lo = mid+1;
}
}
return (int) hi;
}
}
参考资料
《OLAP 性能优化指南》欢迎 Star&共建
欢迎关注微信公众号
