“保留答案的一半”
注意每次的区间左边和右边是是否是闭合的 这关乎每次缩减区间时low和high的取值
找到划分的条件 用什么来区分
使用二分前先将Array Sorted 保留有答案的那一半
4. Median of Two Sorted Arrays
Not a typical binary search problem but we use the idea of divide and conquer. Transfer the problem to "find the kth largest element" of two sorted arrays and each time we compare the A[k/2] with B[k/2] and chop off the range that must not appear in the final list. The idea is "binary search" each time move out the impossible candidate. Use a helper function to accomplish the index move of array.
Another thing to consider is the case when the total length is even or odd. Just use the definition of the "Median"
O(LogN)
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
if((len1+len2)%2 == 1){
return kfind(nums1,nums2,0,0,(len1+len2)/2+1);
}
else{
return (kfind(nums1,nums2,0,0,(len1+len2)/2)+kfind(nums1,nums2,0,0,(len1+len2)/2+1))/2.0;
}
}
public double kfind(int[]nums1,int[]nums2,int s1,int s2,int k){//get the kth large element of elements
//in array nums1 and nums2
//if we have traversed one of the array then just return the kth element directly of another array
if(s1 > nums1.length-1)
return nums2[k+s2-1];
if(s2 > nums2.length-1)
return nums1[k+s1-1];
if(k == 1){
return Math.min(nums1[s1],nums2[s2]);
}
int h1 = Integer.MAX_VALUE;
int h2 = Integer.MAX_VALUE;
//compare the A[mid] with the B[min] and decides whose'half is to be neglected
if(k/2+s1-1 < nums1.length){
h1 = nums1[k/2+s1-1];
}
if(k/2+s2-1 < nums2.length){
h2 = nums2[k/2+s2-1];
}
if(h1 < h2){
return kfind(nums1,nums2,s1+k/2,s2,k-k/2);
}
else{
return kfind(nums1,nums2,s1,s2+k/2,k-k/2);
}
}
}
153. Find Minimum in Rotated Sorted Array
The minimum element must appear in either half, we can compare the middle value with the start and end value. Use JiuZhang's template.
public class Solution {
public int findMin(int[] nums) {
if(nums==null||nums.length==0)return 0;
int start = 0;
int end = nums.length - 1;
while(start + 1 < end){
int mid = start + (end - start)/2;
if(nums[mid] > nums[end]){
start = mid;
}
else{
end = mid;
}
}
return Math.min(nums[start],nums[end]);
}
}
33. Search in Rotated Sorted Array
翻转过后的数组由中间分为两半 一定由一边是有序的~ 所以只要通过比较中间元素和两边的数值就可以得到有序的部分 然后把当前数和有序的两端比较 如果在这个范围 则移动指针到相应的范围 如果不在则说明在另外一边
public class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int low = 0;
int high = n - 1;
while(low <= high){
int mid = low + (high - low)/2;
if(target == nums[mid]){
return mid;
}
else if(nums[mid] < nums[high]){
if(target > nums[mid] && target <= nums[high]){
low = mid + 1;
}
else{
high = mid - 1;
}
}
else{
if(target >= nums[low] && target < nums[mid]){
high = mid - 1;
}
else{
low = mid + 1;
}
}
}
return -1;
}
}
81. Search in Rotated Sorted Array II
有重复数字 导致在判断哪个是严格上升区间的时候变难 如果中间值和两边的相等则需要一步一步移动相应指针 Worst Runtime O(N) Not actually a binary search
public class Solution {
public boolean search(int[] A, int target) {
if (A == null || A.length == 0) {
return false;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
return true;
}
if (A[mid] > A[end]) {
if(target <= A[mid]&&target >= A[start]){
end = mid;
}
else{
start = mid;
}
} else if(A[mid] < A[end]){
if(target <= A[end]&&target >= A[mid]){
start = mid;
}
else{
end = mid;
}
}
//if equal then reduce the search range by one
else{
end--;
}
}
if (A[start] == target) {
return true;
}
if (A[end] == target) {
return true;
}
return false;
}
}
162. Find Peak Element
because the left and right are -∞ so we can decide where the peak goes by comparing the middle element with its neighbors
pay attention it is neighbors! which means we can stop the search for half by only considering middle element and its neighbors
public int findPeakElement(int[] nums) {
int len = nums.length;
int start = 0;
int end = len - 1;
while(start + 1 < end){
int mid = start + (end-start)/2;
//go to left part
if(nums[mid-1] > nums[mid]){
end = mid - 1;
}
//go to right part
else if(nums[mid+1] > nums[mid]){
start = mid + 1;
}
else{
return mid;
}
}
if(nums[start]>nums[end]){
return start;
}
else{
return end;
}
}
278. First Bad Version
if the current mid is bad check left if it's not bad check right until we are left with two remainining element
and it's bad return the index Better to use Jiuzhang's model here
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int low = 1;
int high = n;
while(low + 1 < high){
int mid = low + (high - low)/2;
boolean check = isBadVersion(mid);
if(check == true){
high = mid;
}
else{
low = mid;
}
}
if(isBadVersion(low))return low;
return high;
}
}
74. Search a 2D Matrix
Treat the 2d array as an 1d array and calculate the corresponding row/col index during the comparison
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null||matrix.length==0||matrix[0].length==0)return false;
int m = matrix.length;
int n = matrix[0].length;
int low = 0;
int high = m*n-1;
while(low <= high){
int mid = low + (high - low)/2;
int newRow = mid/n;
int newCol = mid%n;
int val = matrix[newRow][newCol];
if(val == target)return true;
else if(val < target){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return false;
}
}
240. Search a 2D Matrix II
A naive solution is to binary search lines by lines but this solution does not use the benefit of rows/cols sorted. We can instead start searching from the top right corner and rule out a row/col each time by utilizing the given assumptions
How to design a binary search? For a situation we can decide which step to go based on a criteria
If we start searching from the right upper corner then at each step we can go left or go down based
on whether the target value is larger or smaller than the given value
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length < 1 || matrix[0].length <1) {
return false;
}
int col = matrix[0].length-1;
int row = 0;
while(col >= 0 && row <= matrix.length-1) {
if(target == matrix[row][col]) {
return true;
} else if(target < matrix[row][col]) {
col--;
} else if(target > matrix[row][col]) {
row++;
}
}
return false;
}
}
34. Search for a Range
Perform two times Binary Search, first to search the leftmost appearance, second to search the rightmost appearance. 区别就是在于当相等的时候怎样设置指针
public class Solution {
public int[] searchRange(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
int[] result = new int[2];
// find the left most
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){
result[0] = start;
}
else if(nums[end]==target){
result[0] = end;
}
else{
result[0] = result[1] = -1;
return result;
}
start = 0;
end = nums.length - 1;
// find the right most
while(start+1 < end){
int mid = start + (end-start)/2;
if(nums[mid] > target){
end = mid;
}
else if(nums[mid] < target){
start = mid;
}
else{
start = mid;
}
}
if(nums[end]==target){
result[1] = end;
}
else if(nums[start]==target){
result[1] = start;
}
else{
result[0] = result[1] = -1;
return result;
}
return result;
}
}
349. Intersection of Two Arrays
In order to use binary search here. first sort one of the array then compare search each element of the second array's apperance in the first array, if exist just add to a set. Finally add all the element to an array.
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums2);
for (Integer num : nums1) {
if (binarySearch(nums2, num)) {
set.add(num);
}
}
int i = 0;
int[] result = new int[set.size()];
for (Integer num : set) {
result[i++] = num;
}
return result;
}
public boolean binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
}
350. Intersection of Two Arrays II
different from I we need to keep the actual element of intersection!
528. Random Pick with Weight
- Create Presum array to utilize the Internal Random Function
- Pay attention to the binary search range indexes
- JAVA Random function: The nextInt(int n) is used to get a random number between 0(inclusive) and the number passed in this argument(n)
class Solution {
private int[] preSum;
private Random random;
public Solution(int[] w) {
//Initilize
random = new Random();
this.preSum = w;
for(int i = 1;i < w.length;i++){
preSum[i] = preSum[i - 1] + w[i];
}
}
public int pickIndex() {
int sum = preSum[preSum.length - 1];
int pickValue = random.nextInt(sum) + 1;
// find the position of the picked value
// since presum array is sorted
int start = 0;
int end = preSum.length - 1;
while(start < end){
int mid = start + (end - start) / 2;
int midValue = preSum[mid];
if (pickValue > midValue){
start = mid + 1;
}
else if(pickValue < midValue){
end = mid;
}
else{
return mid;
}
}
return start;
}
}