Binary search problems
Today just practice some easy but typical problems, which use both binary search && 2 pointers. Notice how to pick up pivot.
69.Sqrt(x)
Met with this problem in an intrview before and I didn’t notice the type of number at that time…Should use an variable to record the number which is closest to sqrt(x)
each time.
349/167.Two sum in sorted array
Use 2 pointers can be more precise. Notice the condition judgement.
74.Search a 2D matrix
Matrix has property of increasing like a single array. Thus can use binary search directly.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length ==0) return false;
int row = matrix.length, col = matrix[0].length;
int start = 0, end = row*col - 1;
while(start < end) {
int mid = start + (end - start) /2;
if(matrix[mid/col][mid%col] == target) return true;
if(matrix[mid/col][mid%col] < target) {
start = mid + 1;
} else {
end = mid;
}
}
if(start == end && matrix[start/col][start%col] == target) return true;
return false;
}
}
240.Search a 2D matrix
I only make use of the increasing row property, use the right corner as pivot and search entire row or not, which leads to O(mlog(n))
complexity. Better solution is also to use the column increasing property, shrink row/col index by 1 each time, which has O(m+n)
.