In this paper, starting from www.shaotianyu.com/article/5ec…
The goal is to make clear what you know
What does the basic dichotomy look like
In fact, the application scenarios of dichotomy are relatively limited. The most obvious characteristics are:
- In most cases, the search target is monotonically increasing and decreasing.
- There are upper and lower boundaries, and it is desirable to be able to access elements with index subscripts
1.1 From the beginning, basic dichotomy is used
Let’s start with the simplest monotonically increasing array, with the following problem:
Find 4 in [1, 2, 3, 4, 5, 6, 7, 8, 9], return the subscript if it exists, return -1 if it does not exist, require the algorithm complexity O(logn).
The first response to order logn complexity is to use binary search. How do I do that?
First simulate the following general flow of dichotomy on the graph:
According to the diagram, the code is as follows:
function searchNum (target, nums) {
if(! nums.length)return - 1
let left = 0
let right = nums.length - 1
let mid
while (left <= right) {
// >> 1 bit operation instead of division by 2
// Mid = (left+right)/2
mid = left + ((right - left) >> 1)
if (nums[mid] === target) {
return mid
}
if (nums[mid] < target) {
left = mid + 1
}
if (nums[mid] > target) {
right = mid - 1}}return - 1
}
Copy the code1.2 Summary dichotomy routine
From the above question, we can see the routine of point dichotomy. There are laws to follow, and the basic template can be derived:
let left = start
let right = end
let mid
while (left <= right) {
mid = (left + right) / 2
if (array[mid] === target) {
returnThe result orbreak down
}
if (array[mid] < target) {
left = mid + 1
}
if (array[mid] > target) {
right = mid - 1}}Copy the codeOnce we have the basic template for dichotomy, we can then solve the square root of x type problems
Attach the square root of x solution code:
const mySqrt = function(x) {
if (x < 2) return x
let left = 1, mid, right = Math.floor(x / 2);
while (left <= right) {
mid = Math.floor(left + (right - left) / 2)
if (mid * mid === x) return mid
if (mid * mid < x) {
left = mid + 1
}else {
right = mid - 1}}return right
}
Copy the code2. Extension of dichotomy
One of the properties of dichotomy, as I said before, is that it has obvious monotonicity. That’s where our dichotomy template comes in, but there are always special cases.
2.1 Rotate array series I
Find the minimum value in the rotation sort array
Title description:
Suppose the array sorted in ascending order is rotated at some previously unknown point. For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Please find the smallest element. You can assume that there are no duplicate elements in the array.
Solution analysis:
- 1. Solve the problem by violence, traverse the number group and record the minimum value. The time complexity is O(N), where N is the size of the given array
- 2. Dichotomy, time complexity is O(logN),
How do we use dichotomy here? How to use the properties of dichotomy properly? How to improve the consistent dichotomy?
2.1.1 Tear off the coat of rotation array and parse its rules
If we want to break down the problem, the premise of the problem is that the array is sorted in ascending order and rotated at some unknown point, then we need to consider how to determine whether the array is sorted in ascending order or has been rotated out of order. Let’s draw a picture:
According to the above picture, we can intuitively see a rule, how to determine whether it is disrupted by rotation? The normal ascending condition is first element < last element, and the out-of-order condition is first element > last element
And then continue to dig the rule of the disorderly number group, that is the order in the chaos, how to understand?
Notice that the left and right sides of the dotted black line are in ascending order, and the dotted black line, which is the Point that the red arrow points to, we can think of as the dividing Point, which is used to divide two ascending arrays.
So we can summarize the following rules:
- 1. The element to the left of the demarcation point >= the first element
- 2. The element to the right of the cut-off point < the first element
So, going back to the problem, our starting point was to find the smallest value in the array, so now, what can we find? We can look for the cutoff point, the cutoff point is found, the minimum is right next to the cutoff point, the minimum is found incidentally.
The key to the problem is found, how to find the cut-off point?
Ideas:
Step 1: Based on the idea of dichotomy, find mid first
If mid > first element, what does it mean? Mid + 1 = mid + 1 = mid + 1 = mid + 1
Step 3: If mid < first element, what does that mean? That means that the minimum must be to the left of mid, and in this case, we need to look to the left of mid, so right is equal to mid-1
Step 4: What are the termination conditions? There are two cases to discuss:
- If mid > mid + 1, then mid + 1 is the minimum value
- 2, if mid < mid – 1, mid is the minimum value, return the result
The overall idea is clear, the code is simple:
const findMin = function (nums) {
if(! nums.length)return null
if(nums.length === 1) return nums[0]
let left = 0, right = nums.length - 1, mid
// If the array is monotonically increasing, the first element is the minimum
if (nums[right] > nums[left]) return nums[0]
while (left <= right) {
mid = left + ((right - left) >> 1)
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1]}if (nums[mid] < nums[mid - 1]) {
return nums[mid]
}
if (nums[mid] > nums[0]) {
left = mid + 1
} else {
right = mid - 1}}return null
}
Copy the code2.2 Rotate array series II
Search rotated sorted arrays
Title description:
Suppose the array sorted in ascending order is rotated at some previously unknown point. For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Searches for a given target value, returning its index if it exists in the array, or -1 otherwise. You can assume that there are no duplicate elements in the array. Your algorithm must be order log n in time.
Algorithm time complexity must be O(log n) level, binary search.
There are many ways to solve this problem. The following are two common ones:
- 1. According to the index of the minimum value of 2.1, divide the array into two parts of the ordered array, and then determine target in accordance with the comparison relation between num[0] and target
Cut-off pointTo the left or right of, and then do a binary lookup on the corresponding side of the ascending array - 2. Perform binary search directly on the array, and then determine in the search
Cut-off pointBoundary relation of
If we use method 2, how do we determine the boundary in binary search?
According to the above 2.1,
If mid > first element, the left side of mid is in ascending order. If mid < first element, it indicates that the right side of MID is in ascending order. According to this rule, we can distinguish two ascending array segments, and then conduct binary search in the corresponding ascending range, and constantly adjust the position of left and right
We can write the idea of this problem first, the idea is clear, the code is simple:
Ideas:
Step 1: Based on the idea of dichotomy, find mid first
Step 2: Judge the size relationship between MID and first element and determine the interval where MID is located
Step 3: Discuss in two parts:
- If target >= left (mid) and target < mid (left, mid), select right = mid-1. [mid, right] = mid + 1;
- [mid, left = mid + 1] [mid, left = mid + 1] [mid, left = mid + 1] [mid, right] [left, mid] = mid -1 [left, mid] = mid -1
- The terminating condition is mid element === target, end
const search = function(nums, target) {
if(! nums.length)return - 1
let left = 0, right = nums.length - 1, mid
while (left <= right) {
mid = left + ((right - left) >> 1)
if (nums[mid] === target) {
return mid
}
if (nums[mid] >= nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1
} else {
left = mid + 1}}else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1
} else {
right = mid - 1}}}return - 1
}
Copy the code2.3 Rotate array series III
Search rotated sorted array II
Title description:
Suppose the array sorted in ascending order is rotated at some previously unknown point. For example, the array [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]. Write a function to determine whether a given target value exists in an array. Return true if it exists, false otherwise.
The topic is a variation of 2.2, and the idea is similar.
The difference here is that the array has repeating elements, so how do we get rid of repeating elements? For an array like [1,3,1,1,1], it is difficult to define two ascending ranges by comparing mid and left elements, but we can eliminate duplicates by constantly comparing mid and left elements to see if they are the same.
Train of thought
If mid element === left element: it indicates that there are repeated items. Adjust the left pointer to move left to the right to remove repeated interferenceCopy the codeTranslate the above idea into code and add it to 2.2 to get the solution:
const search = function(nums, target) {
if(! nums.length)return false
let left = 0, right = nums.length - 1, mid
while (left <= right) {
mid = left + ((right - left) >> 1)
if (nums[mid] === target) {
return true
}
if (nums[left] === nums[mid]) {
++left
continue
}
if (nums[mid] >= nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1
} else {
left = mid + 1}}else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1
} else {
right = mid - 1}}}return false
}
Copy the codeSuccessful AC –
Execution time :56 ms, beating 98.31% of users in all JavaScript commits
3 summary
Above is a summary of the basic use cases of dichotomy, and the basic routines of the rotated array series. There are many classic cases of dichotomy, which will be added later.
Personal ability is limited, if there is insufficient, also hope to point out. 3 q.