Dichotomy is a type of problem that we often encounter when we do algorithm exercises, but about dichotomy, do you really, really know how to use it?
I couldn’t figure out the interval definition in those years
When faced with an ordered array, we first consider whether we can use dichotomy to solve the corresponding problem. But while dichotomy is simple to use, it is relatively easy to understand. However, when we first use it, we often have various problems. For example, should the termination condition in while be < or <=? When I redefine left and right, is it mid or is it mid+1? If we don’t judge these problems properly, our code will often have various bugs and even an endless loop.
So how to solve this problem? The most important thing is to understand the interval definition of dichotomy in use
There are many templates for dichotomy on the Internet, but rote memorization is not the ultimate solution; And it’s really easy to understand, just in one sentence, to think about whether our interval is valid or not
// For the array nums
let left = 0;
let right = nums.length [left,right] [nums.length] [left,right]
while(left < right) // if left = right, the interval looks like [1,1]. The interval is invalid
let left = 0;
let right = nums.length - 1 [left,right]
while(left <= right) // when left = right, the interval looks like this [1,1], the interval is still valid, and the code continues to execute
Copy the code[left,right] = [left,right] = [left,right] = [left,right] = [left,right]
Let’s do another example, let’s see when plus 1, and when we don’t need plus 1
35. Search for insert Location – LeetCode (leetcode-cn.com)
Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length
while(left < right){ [left,right]
let mid = Math.floor((left+right)/2)
if(nums[mid]===target) return mid
if(nums[mid] < target) left = mid + 1; // If nums[mid] < target, mid + 1 is left
if(nums[mid] > target) right = mid; // if nums[mid] > target, the value of mid is not in the range
}
return left;
};
Copy the codeIf you understand the code above, look again
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length - 1
while(left <= right){ [left,right]
let mid = Math.floor((left+right)/2)
if(nums[mid]===target) return mid
if(nums[mid] < target) left = mid + 1; // Mid is already in the interval, so mid + 1 is needed
if(nums[mid] > target) right = mid - 1; // Mid does not satisfy the condition, but right is also in the interval, so we need mid-1
}
return left;
};
Copy the codeBoth pieces of code have the same effect
In short, you need +1 or -1 based on whether left and right are valid in the interval
But it is only the simplest case, different topics also need specific analysis, in fact, as long as the understanding, no matter how complex the situation can also be cleverly dealt with.
Return left or right
In some questions, not can find our target, that is no mid meet the conditions, this time topic often tell us, if this is what we need to return, or insert elements of the example above, if not, we will return to the target element is inserted into a position, or is to find the square root, If the square of 8 is not an integer, take 2;
69. Square Root of x – Force Buckle (LeetCode) (leetcode-cn.com)
const mySqrt = x= > {
let [left, right] = [0, x];
while (left <= right) {
const mid = Math.floor((left+right)/2);
if (mid * mid > x) {
right = mid - 1;
} else if (mid * mid < x) {
left = mid + 1;
} else {
returnmid; }}return right;
};
Copy the codeNotice that when we insert the element, we return left, and over here we return right.
In fact, there is no rule, even the same problem, different codes may return different; The only way to solve this is to analyze it, and I usually do an example, like the square root of 8 here, and then I draw a picture, and I follow the code, and eventually you’ll see which one you get back.
Binary topic summary in LeetCode
35. Search for insert Location – LeetCode (leetcode-cn.com)
I’ve already written the code above, so I won’t waste space here
240. Searching the Two-dimensional Matrix II – Force Buckle (LeetCode) (leetcode-cn.com)
Start from the lower left corner, less than the target value row -, greater than the target value col++
var searchMatrix = function(matrix, target) {
let maxI = matrix.length - 1;
let maxJ = matrix[0].length-1;
let i = maxI;
let j = 0;
while(i>=0 && j<=maxJ){
let cur = matrix[i][j]
if(cur<target) j++
else if(cur>target) i--
else return true;
}
return false
};
Copy the codeFind the first and last position of an element in a sorted array
Specific idea: binary traversal first to find a target value, and then left, right expansion
var searchRange = function(nums, target) {
let [left,right,flag] = [0,nums.length,null]
while(left < right){
let mid = Math.floor((left+right)/2)
if(nums[mid] === target){
flag = mid;
break;
}
else if(nums[mid]<target) left = mid + 1;
else right = mid
}
if(flag == null) return [-1, -1]
left = right = flag
while(nums[left - 1] === target) left--;
while(nums[right + 1] === target) right++;
return [left,right]
};
Copy the code162. Finding Peaks – LeetCode (leetcode-cn.com)
Specific idea: traversal, the condition is set as mid is greater than mid+1; Note that left<right, otherwise there will be an endless loop, how is thought to know.
var findPeakElement = function(nums) {
let left = 0;
let right = nums.length-1;
while(left<right){
let mid = Math.floor((left+right)/2)
if(nums[mid]>nums[mid+1]) right = mid
else left = mid + 1
}
return right
};
Copy the code153. Find the minimum value in the rotation sort array – LeetCode (leetcode-cn.com)
If the current value is less than the rightmost value, the minimum value is to the left of mid or mid. If the current value is greater than or equal to the rightmost value, the minimum value is to the right of mid and cannot be mid
var findMin = function(nums) {
let left = 0;
let right = nums.length -1;
while(left<=right){
let mid = Math.floor((left+right)/2)
if(nums[mid]<nums[right]) right = mid
else left = mid + 1
}
return nums[right]
};
Copy the code275. H Index II – LeetCode (leetcode-cn.com)
Mid = mid = mid = mid = mid = mid = mid = mid = mid = mid But notice that the final value is h, which means it doesn’t have to be any number in our array, it just means there are at least a few of them.
var hIndex = function(citations) {
const len = citations.length
let left = 0;
let right = len -1;
let res = 0;
while(left <= right){
let mid = Math.floor((left+right)/2)
if(citations[mid]>=(len - mid)){
res = len - mid
right = mid - 1
}else left = mid + 1
}
return res
};
Copy the code300. Longest Increasing Subsequence – LeetCode (leetcode-cn.com)
If the current element is larger than the largest element in the array, put it directly into the array. If less than or equal to, then find a place in the array to insert it. (Note that the new array may not be the correct array in the result, but the length is the same, so this dichotomy is only one of the solutions, not the optimal solution)
var lengthOfLIS = function(nums) {
if(nums.length === 1) return 1;
const arr = [nums[0]]
for(let i = 1; i<nums.length; i++){if(nums[i]>Math.max(... arr)){ arr.push(nums[i]) }else{
let left = 0
let right = arr.length
while(left < right){
let mid = Math.floor((right+left)/2)
if(nums[i] > arr[mid]) left = mid + 1
else right = mid
}
arr[left] = nums[i]
}
}
return arr.length
};
Copy the codeFinally, after you did a few topics, discover dichotomy is not difficult actually, it is important to understand the meaning of the topic, make out the condition in dichotomy can, flexible use, square is the truth!!