# LintCode二分查找题总结

LC上二分查找那一章有这么些题：

457. Classical Binary Search

``````    public int findPosition(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
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;
}
if (A[end] == target) {
return end;
}
return -1;
}``````

14. First 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 {
start = mid;
}
}

if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}``````

458. Last Position of Target

``````    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 {
end = mid;
}
}

if (nums[end] == target) {
return end;
}
if (nums[start] == target) {
return start;
}
return -1;
}``````

459. Closest Number in Sorted Array

Given `[1, 4, 6]` and target = `3`, return `1`.

Given `[1, 4, 6]` and target = `5`, return `1` or `2`.

Given `[1, 3, 3, 4]` and target = `2`, return `0` or `1` or `2`.

``````    public int closestNumber(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
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;
}
}
int left = Math.abs(A[start] - target);
int right = Math.abs(A[end] - target);
return left < right ? start : end;
}``````

462. Total Occurrence of Target

``````    public int totalOccurrence(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) {
start = mid;
} else {
end = mid;
}
}
int count;
if (A[start] == target) {
count = 0;
for (int i = start; i < A.length; i++) {
if (A[i] == target) {
count++;
}
}
return count;
}
if (A[end] == target) {
count = 0;
for (int i = end; i < A.length; i++) {
if (A[i] == target) {
count++;
}
}
return count;
}
return 0;
}``````

60. Search Insert Position

[1,3,5,6]，5 → 2

[1,3,5,6]，2 → 1

[1,3,5,6]，7 → 4

[1,3,5,6]，0 → 0

``````    public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (target <= nums[start]) {
return start;
}
if (target <= nums[end]) {
return end;
}
return end + 1;
}``````

28. Search a 2D Matrix

``````    public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int m = matrix.length;
int n = matrix[0].length;
if (n == 0) {
return false;
}

int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[mid/n][mid%n] == target) {
return true;
} else if (matrix[mid/n][mid%n] < target) {
left = mid + 1;
} else if (matrix[mid/n][mid%n] > target) {
right = mid - 1;
}
}
return false;
}``````

547. Intersection of Two Arrays

``````    public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}

HashSet set1 = new HashSet();
for (int i = 0; i < nums1.length; i++) {
}

HashSet res = new HashSet();
for (int i = 0; i < nums2.length; i++) {
if (set1.contains(nums2[i]) && !res.contains(nums2[i])) {
}
}

int[] result = new int[res.size()];
int index = 0;
for (Integer tmp : res) {
result[index] = tmp;
index++;
}

return result;
}``````

548. Intersection of Two Arrays II

``````    public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}
HashMap map = new HashMap();
for (int i = 0; i < nums1.length; i++) {
if (map.containsKey(nums1[i])) {
map.put(nums1[i], 1 + map.get(nums1[i]));
} else {
map.put(nums1[i], 1);
}
}

ArrayList res = new ArrayList();
for (int i = 0; i < nums2.length; i++) {
if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
map.put(nums2[i], map.get(nums2[i]) - 1);
}
}

int[] result = new int[res.size()];
for (int i = 0; i < result.length; i++) {
result[i] = res.get(i);
}
return result;
}``````

141. Sqrt(x)

``````    public int sqrt(int x) {
long start = 0, end = x;
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (mid * mid > x) {
end = mid;
} else if (mid * mid == x) {
return (int)mid;
} else {
start = mid;
}
}
if (start * start <= x && end * end > x) {
return (int)start;
}
return (int)end;
}``````

586. Sqrt(x) II

``````public class Solution {
/**
* @param x a double
* @return the square root of x
*/
public double sqrt(double x) {
return binary_search_sqrt(x);
}
public double newton_sqrt(double n) {
double result = 1.0;
double eps = 1e-12;
while (Math.abs(result * result - n) > eps) {
result = (result + n / result) / 2;
}
return result;
}
public double binary_search_sqrt(double n) {
double start = 0, end = n > 1 ? n : 1.0;
while (end - start > 1e-12) {
double mid = (start + end) / 2;
if (mid * mid > n) {
end = mid;
} else {
start = mid;
}
}
return start;
}
}``````

428. Pow(x, n)

``````    public double myPow(double x, int n) {
if (n == 0) {
return 1.0;
}
if (n < 0) {
return 1.0/myPow(x, -n);
}
return x * myPow(x, n - 1);
}``````

``````    public double myPow(double x, int n) {
if (n == 0) {
return 1.0;
}
if (n < 0) {
return 1.0/myPow(x, -n);
}
double half = myPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
}
return x * half * half;
}``````

``````    public int findFirstBadVersion(int n) {
int start = 1, end = n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
start = mid;
} else {
end = mid;
}
}
return start;
} else {
return end;
}
}``````

75. Find Peak Element

1）mid落在了上升区间，那这个时候的峰值肯定在mid右边的区间

2）mid落在了下降区间，那这个时候的峰值肯定在mid左边的区间

3）mid就在峰值，那就直接return

4）mid在极小值，那就随便往右边或者往左边走都行

``````    public int findPeak(int[] A) {
int start = 0, end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid - 1] <= A[mid] && A[mid] <= A[mid + 1]) {
start = mid;
continue;
}
if (A[mid - 1] >= A[mid] && A[mid] >= A[mid + 1]) {
end = mid;
continue;
}
if (A[mid - 1] <= A[mid] && A[mid] >= A[mid + 1]) {
return mid;
}
end = mid;
}
if (A[start] < A[end]) {
return end;
}
return start;
}``````

61. Search for a Range

``````    public int[] searchRange(int[] A, int target) {
int[] res = new int[2];
if (A == null || A.length == 0) {
return new int[]{-1, -1};
}
int start = 0, end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[start] == target) {
res[0] = start;
for (int i = start; i < A.length; i++) {
if (A[i] == target) {
res[1] = i;
}
}
return res;
}
if (A[end] == target) {
res[0] = end;
for (int i = end; i < A.length; i++) {
if (A[i] == target) {
res[1] = i;
}
}
return res;
}
return new int[]{-1, -1};
}``````

447. Search in a Big Sorted Array

``````    public int searchBigSortedArray(ArrayReader reader, int target) {
int index = 1;
while (reader.get(index - 1) < target && reader.get(index - 1) != -1) {
index *= 2;
}
int start = 0, end = index - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
end = mid;
continue;
}
start = mid;
} else {
end = mid;
}
}

return start;
}
return end;
}
return -1;
}``````

159. Find Minimum in Rotated Sorted Array

``````    public int findMin(int[] num) {
if (num == null || num.length == 0) {
return -1;
}
int start = 0, end = num.length - 1;
if (num[end] > num[start]) {
return num[start];
}
int target = num[end];
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (num[mid] <= target) {
end = mid;
} else {
start = mid;
}
}
if (num[start] <= target) {
return num[start];
} else {
return num[end];
}
}``````

160. Find Minimum in Rotated Sorted Array II

62. Search in Rotated Sorted Array

``````    public int search(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
int start = 0, 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]) {
if (A[start] <= target && target <= A[mid]) {
end = mid;
} else {
start = mid;
}
} else { // 右边上升区间
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;
}``````

63. Search in Rotated Sorted Array II

38. Search a 2D Matrix II

``````[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]``````

``````    public int searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
if (n == 0) {
return 0;
}
int x = m - 1;
int y = 0;
int count = 0;
while (x >= 0 && y < n) {
if (matrix[x][y] < target) {
y++;
} else if (matrix[x][y] > target) {
x--;
} else {
count++;
x--;
y++;
}
}
return count;
}``````

460. K Closest Numbers In Sorted Array

``````    // find the first index of element >= target
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) {
end = mid;
} else {
start = mid;
}
}

if (A[start] >= target) {
return start;
}
if (A[end] >= target) {
return end;
}
return A.length;
}

public int[] kClosestNumbers(int[] A, int target, int k) {
if (A == null || A.length == 0) {
return A;
}
if (k > A.length) {
return A;
}
int index = firstIndex(A, target);

int start = index - 1, end = index;
int[] res = new int[k];
for (int i = 0; i < k; i++) {
if (start < 0) {
res[i] = A[end++];
} else if (end >= A.length) {
res[i] = A[start--];
} else {
if (target - A[start] <= A[end] - target) {
res[i] = A[start--];
} else {
res[i] = A[end++];
}
}
}
return res;
}``````

183. Wood Cut

For L=[232, 124, 456], k=7, return 114. 比如给了你三块长度分别为232、124、456的木头，你需要把他们均分成7块等长的木头，并且保证木头长度最大。

``````    private int count(int[] L, int n) {
int res = 0;
for (int i = 0; i < L.length; i++) {
res += L[i] / n;
}
return res;
}
public int woodCut(int[] L, int target) {
int max = 0;
for (int i = 0; i < L.length; i++) {
max = Math.max(max, L[i]);
}
int start = 1, end = max;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (count(L, mid) < target) {
end = mid;
} else {
start = mid;
}
}
if (count(L, end) >= target) {
return end;
}
if (count(L, start) >= target) {
return start;
}
return 0;
}``````

248. Count of Smaller Number

``````    private int count(int[] num, int target) {
if (num == null || num.length == 0) {
return 0;
}
int start = 0, end = num.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target <= num[mid]) {
end = mid;
} else {
start = mid;
}
}
if (num[start] >= target) {
return start;
}
if (num[end] >= target) {
return end;
}
return 0;
}
public ArrayList countOfSmallerNumber(int[] A, int[] queries) {
Arrays.sort(A);
ArrayList res = new ArrayList();
for (int i = 0; i < queries.length; i++) {
int n = count(A, queries[i]);
}
return res;
}``````

633. Find the Duplicate Number

``````public class Solution {
/**
* @param nums an array containing n + 1 integers which is between 1 and n
* @return the duplicate one
*/
public int findDuplicate(int[] nums) {
int start = 1, end = nums.length - 1;
while (start + 1 < end) {
int mid = (start + end) / 2;
if (checkSmaller(nums, mid) <= mid) {
start = mid;
} else if (checkSmaller(nums, mid) > mid) {
end = mid;
}
}
if (checkSmaller(nums, start) > start) {
return start;
}
return end;
}

public int checkSmaller(int[] nums, int target) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= target) {
count++;
}
}
return count;
}
}``````

617. Maximum Average Subarray

``````    public boolean checkRest(int[] nums, int k, double mid) {
double[] sum = new double[nums.length + 1];
sum[0] = 0;
for (int i = 1; i <= nums.length; i++) {
sum[i] = sum[i - 1] + nums[i - 1] - mid;
if (i >= k) {
if (sum[i] - badAss >= 0) {
return true;
}
}
}
return false;
}
public double maxAverage(int[] nums, int k) {
double min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= max) {
max = nums[i];
}
if (nums[i] <= min) {
min = nums[i];
}
}

while (max - min > 1e-6) {
double mid = (min + max) / 2.0;
if (checkRest(nums, k, mid)) {
min = mid;
} else {
max = mid;
}
}

return min;
}``````

600. Smallest Rectangle Enclosing Black Pixels

``````"000000111000000"
"000000101000000"
"000000101100000"
"000001100100000"``````

``"000001111100000"``

row search为例， 所有含有black pixel的column，映射到row x上时，必定是连续的。这样我们可以使用binary search，在0到y里面搜索最左边含有black pixel的一列。接下来可以继续搜索上下和右边界。

``````public class Solution {
/**
* @param image a binary matrix with '0' and '1'
* @param x, y the location of one of the black pixels
* @return an integer
*/
public int minArea(char[][] image, int x, int y) {
if (image == null || image.length == 0) {
return 0;
}
int left = binarySearchLeft(image, 0, y);
int right = binarySearchRight(image, y, image[0].length - 1);
int high = binarySearchHigh(image, x, image.length - 1);
int low = binarySearchLow(image, 0, x);
return (right - left + 1) * (high - low + 1);
}

public int binarySearchLeft(char[][] image, int left, int right) {
while (left + 1 < right) {
int mid = (left + right) / 2;
boolean black_flag = false;
for (int i = 0; i < image.length; i++) {
if (image[i][mid] == '1') {
black_flag = true;
break;
}
}
if (black_flag) {
right = mid;
} else {
left = mid;
}
}
for (int i = 0; i < image.length; i++) {
if (image[i][left] == '1') {
return left;
}
}
return right;
}

public int binarySearchRight(char[][] image, int left, int right) {
while (left + 1 < right) {
int mid = (left + right) / 2;
boolean black_flag = false;
for (int i = 0; i < image.length; i++) {
if (image[i][mid] == '1') {
black_flag = true;
break;
}
}
if (black_flag) {
left = mid;
} else {
right = mid;
}
}
for (int i = 0; i < image.length; i++) {
if (image[i][right] == '1') {
return right;
}
}
return left;
}

public int binarySearchHigh(char[][] image, int left, int right) {
while (left + 1 < right) {
int mid = (left + right) / 2;
boolean black_flag = false;
for (int i = 0; i < image[0].length; i++) {
if (image[mid][i] == '1') {
black_flag = true;
break;
}
}
if (black_flag) {
left = mid;
} else {
right = mid;
}
}
for (int i = 0; i < image[0].length; i++) {
if (image[right][i] == '1') {
return right;
}
}
return left;
}

public int binarySearchLow(char[][] image, int left, int right) {
while (left + 1 < right) {
int mid = (left + right) / 2;
boolean black_flag = false;
for (int i = 0; i < image[0].length; i++) {
if (image[mid][i] == '1') {
black_flag = true;
break;
}
}
if (black_flag) {
right = mid;
} else {
left = mid;
}
}
for (int i = 0; i < image[0].length; i++) {
if (image[left][i] == '1') {
return left;
}
}
return right;
}

}``````

390. Find Peak Element II

``````    public List findPeakII(int[][] A) {
List res = new ArrayList();
int low = 1, high = A.length - 2;
while (low <= high) {
int mid = (low + high) / 2;
int col = findPeak(A, mid);
if (A[mid][col] < A[mid - 1][col]) {
high = mid - 1;
} else if (A[mid][col] < A[mid + 1][col]) {
low = mid + 1;
} else {
return res;
}
}
return res;
}
public int findPeak(int[][] A, int row) {
int col = 0;
for (int i = 0; i < A[row].length; i++) {
if (A[row][i] > A[row][col]) {
col = i;
}
}
return col;
}
``````