This introduction is also based on Mr. Wang Zheng's course ～～
The beauty of data structure and algorithm
Make your own summary and thinking
1、 The dichotomy you and I both know
It is an algorithm for finding data , skill . The whole process is as like as two peas. , It means ,“ Divide the data in half , And then find ”.
Universal example , Guess the number ～！
You think of a 0～1000 The number of .
Let me guess , I say one number at a time , You sue me , The relationship between my number and the target number .
First, subconsciously think , It seems hard to guess ,1000 A digital , You have to guess a hundred times . In fact, learn this skill , The worst is just 10 Time , Absolutely guess ！！！.
such as , The number you think is 126.
Guess for the first time ：500 answer ： Your number is too big .
Second guess ：250 answer ： The number you said is still big .
Guess for the third time ：125 answer ： The number you said is too small （ Ouch, it's close ）
Guess for the fourth time ：187 answer ： big
Guess for the fifth time ：156 answer ： big
Guess for the sixth time ：140 answer ： Still big
Guess for the seventh time ：132 answer ： Still big
Guess for the eighth time ：128 answer ： Still big （ It's over. Guess ）
Guess for the ninth time ：126
Copy code
Whatever number you want ,10 You can definitely guess in one time .
Why does this happen ？ Why? 1001 A digital , Why 10 And then ？
In fact, take a serious look at the process of guessing , And look at the title of this article , Two, two ～～～！ You can feel .
Game script
Guess in the middle ！！！！！！
 Just guess the middle number in the known range every time
 If you know all the numbers and even numbers of the range , such as 0～9, Just guess the middle 4（0,1,2,3,4,5,6,7,8,9）
 If all numbers in the range are odd , such as 5～8, You take the middle , Rounding down ,6
Actual development scenarios
such as , Yes 1001 Order data , According to the amount of the order , From small to large . We need to find out if the amount is 100 Meta data .
The order data is stored in an array .
Common sense directly traverses the array , Amount, if any 100, We'll go back to true La . At worst , We may have to traverse the entire array ,
The time complexity is O(n).
But we use dichotomy to , Find only half of the data at a time , Until my data range is only one .
range：1001/2
range：1001/2/2
...
range：1
According to this calculation logic, we can know , most 2 Of 10 Power , because 2 Of 10 The power is 1024.
therefore Time complexity can go to O(logn)
Two points search , efficiency O(logn)
Code logic
left The pointer is the left interval ,right Is the right interval , In the middle of each guess mid
mid = Math.floor((left + right)/2)
 Loop to find the middle point of a known interval , In fact, it is to adjust the interval according to the results every time
2、 The implementation of binary search
Simple and easy to understand , Go straight to the code .
Find a value in an ordered array , There are no duplicate elements in the array .
const arr = [1,3,4,5,7,...]
function bsearch(arr,num){
let left = 0
let right = arr.length  1
while(left <= right){
let mid = left + Math.floor((right  left) / 2)
if(arr[mid] === num) return mid
else if (arr[mid] > num){
right = mid  1
}else if (arr[mid] < num){
left = mid + 1
}
}
return 1
}
bsearch(arr, 3)
Copy code
Key logical points
 The loop condition
left <= right
If it isleft < right
When [1,2], The number we're looking for is 2 When ,mid = 0,arr[mid] < 2,left = 0 + 1,
here ,left === right
, Out of the loop . You can't find the subscript is right The right result .  Update of interval boundary
left and right Pointer update ,right = mid  1,left = mid + 1
It may appear that it will be written asright = mid,left = mid
The situation of , If so, when left === right, It falls into an infinite cycle , Can't quit while.
3、 Limitations of binary search
 Binary search order dependent storage structure , Array
Because the main core logic is to find the element with the middle subscript , So the data structure should support random access elements . Arrays support random access , And the time complexity is O(1)  Binary search algorithm needs to act on ordered data
If the data is out of order , We can't compare the size , Continuous interval left、right Modification of .  The right amount of data
A small amount of data is about ten digits , At this time, it doesn't make any difference to traverse directly . But too much data will also affect memory space , Because the array structure , The application of memory requires a large amount of continuous space
4、 Binary search deformation
The basic implementation of binary search , For you, so easy La . Let's take a look at other deformation logic, which is also very common .
The premise of the following deformation is
Exists in an ordered array of repeating elements
Find the first element with the given value
Look directly at the code and then
function bsearch(arr,num){
let left = 0
let right = arr.length  1
while(left <= right){
let mid = left + Math.floor((right  left) / 2)
if (arr[mid] > num){
right = mid  1
}else if (arr[mid] < num){
left = mid + 1
}else {
if(mid === 0  arr[mid  1] < num) return mid
else right = mid  1
}
}
return 1
}
Copy code
The difference between this logic and the basic dichotomy is
if (arr[mid] === num){
if(mid === 0  arr[mid  1] < num) return mid
else right = mid  1
}
Copy code
When the same value is found , Don't rush back , But to judge whether it is the first element , Or whether the previous element is smaller than the given value , If so , Proof is the first element to appear .
Find the last element with the given value
function bsearch(arr,num){
let left = 0
let right = arr.length  1
while(left <= right){
let mid = left + Math.floor((right  left) / 2)
if (arr[mid] > num){
right = mid  1
}else if (arr[mid] < num){
left = mid + 1
}else {
if(mid === arr.length  1  arr[mid + 1] > num) return mid
else left = mid + 1
}
}
return 1
}
Copy code
Find the first element greater than or equal to the given value
function bsearch(arr,num){
let left = 0
let right = arr.length  1
while(left <= right){
let mid = left + Math.floor((right  left) / 2)
if (arr[mid] >= num){
if(mid === 0  arr[mid  1] < num){
return mid
}
right = mid  1
}else if (arr[mid] < num){
left = mid + 1
}
}
return 1
}
Copy code
leetcode actual combat
Whenever you encounter ordered data , Can support random subscript access , Find an element . Then you can think of dichotomy .
Whenever you encounter ordered data , Can support random subscript access , Find an element . Then you can think of dichotomy .
Whenever you encounter ordered data , Can support random subscript access , Find an element . Then you can think of dichotomy .
69. x The square root of
Let's look at the simple question first , There are many pits .
problem ：
Realization int sqrt(int x) function . Calculate and return x The square root of , among x Is a nonnegative integer . Because the return type is an integer , The result only keeps the whole number part , The decimal part will be removed .
Example ：
Input : 4
Output : 2
Input : 8
Output : 2
explain : 8 The square root of is 2.82842...,
Because the return type is an integer , The decimal part will be removed .
Copy code
Ideas ：
Disassemble the meaning of the title
 Find a number N
 Because the decimal part of the search value is omitted , be
N*N <= X
X >= 0
Numbers , Natural is an ordered data , That's from 0~X, Find a number N*N <= X
.
Let's start with the simple .
If it's looking for N*N === X
, Found return , No return found 1, Is the most basic dichotomy
var mySqrt = function (x) {
let [left, right] = [0, x]
while (left <= right) {
let mid = Math.floor((right  left) / 2) + left
if (mid * mid < x) {
left = mid + 1
} else if (mid * mid > x) {
right = mid  1
} else {
return mid
}
}
return 1
};
Copy code
But if we don't find it, we have to return one N*N <= X Of N value .
Think about it , The last logic before exiting the loop must be left = mid + 1
or right = mid  1
, The key points are mid.
If mid * mid > X, Exit loop . Then the closest value must be mid  1.
If mid * mid < X, left > right, Exit the loop when the interval is exceeded . That can only be mid 了 .
so, Code ：
var mySqrt = function (x) {
// Find a number n, n*n Nearest x, But not more than
let [left, right] = [0, x]
let mid
while (left <= right) {
mid = Math.floor((right  left) / 2) + left
if (mid * mid < x) {
left = mid + 1
} else if (mid * mid > x) {
right = mid  1
} else {
return mid
}
}
return mid * mid > x ? mid  1 : mid
};
Copy code
81. Search rotation sort array II
problem ：
It is known that there is an array of integers in non descending order nums , The values in the array don't have to be different from each other .
Before passing it to a function ,nums In some unknown subscript k（0 <= k < nums.length） On the rotate , Make array [nums[k], nums[k+1], ..., nums[n1], nums[0], nums[1], ..., nums[k1]]（ Subscript from 0 Start Count ）. for example , [0,1,2,4,4,4,5,6,6,7] In subscript 5 It may turn into [4,5,6,6,7,0,1,2,4,4] .
Here you are. After rotation Array of nums And an integer target , Please write a function to determine whether the given target value exists in the array . If nums There is a target value in target , Then return to true , Otherwise return to false .
Example ：
Input ：nums = [2,5,6,0,0,1,2], target = 0
Output ：true
Input ：nums = [2,5,6,0,0,1,2], target = 3
Output ：false
Tips ：
1 <= nums.length <= 5000
104 <= nums[i] <= 104
Topic data assurance nums Rotated on a previously unknown subscript
104 <= target <= 104
Copy code
Ideas ：
Look at the ordered array , Look for elements . Dichotomy ～～！ Look down , This is one of the ways to solve problems
But the question is so long , There are still two doubts
 The title rotates the array at a certain point . In this way, the array is not a complete ordered array .
 There will be duplicate elements , But the problem is to find out whether a given value exists ？ Act of bewilderment . This will not affect the logic of dichotomy at all , The most basic dichotomy can be realized . If it's a repeating element , Find the first one , It may involve the deformation of dichotomy .
Then let's find a way to solve the first doubt .nums = [2,5,6,0,0,1,2]
Look at this example array , In fact, if we first divide it into two intervals by dichotomy, what will it become ？[2,5,6,0] [0,1,2]
, Ah , At least one of these arrays is ordered , Because the title is only in a subscript “ rotate ”. So one of the ordered arrays , We can solve it by dichotomy . Let's see what happened to the interval on the left .
That's not the same , In two .[2,5] [6,0]
Until we split the interval to only one or two elements , Just judge directly and return . Let's also review the idea of recursion .
Think about it
 Divide the array in half
 Judge whether one group is orderly , Use the basic dichotomy to directly search for elements and return results
 The other group is not orderly , If the length is small , One or two , You can judge directly and return . If the length is long , Repeat the first step logic .
Code ：
var search = function (nums, target) {
// Binary array , Find an orderly , A period of disorder
function mySplit(l, r) {
if(l > r)return false
let mid = Math.floor(l + (r  l) / 2)
if(nums[mid] === target) return true
// The tail is larger than the head , It must be an ordered interval
if (nums[l] < nums[mid]) {
// Orderly
const res = find(l, mid  1)
if (res) return res
} else {
// disorder , recursive
const res = mySplit(l, mid  1)
if (res) return res
}
if (nums[mid + 1] < nums[r]) {
const res = find(mid + 1, r)
if (res) return res
} else {
const res = mySplit(mid + 1, r)
if (res) return res
}
return false
}
function find(start, end) {
if (nums[start] > target  nums[end] < target) return false
while (start <= end) {
let mid2 = Math.floor(start + (end  start) / 2)
if (nums[mid2] === target) {
return true
}
if (nums[mid2] > target) end = mid2  1
if (nums[mid2] < target) start = mid2 + 1
}
return false
}
// Receive the leading and trailing subscripts for segmentation
return mySplit(0, nums.length  1)
};
Copy code
74. Search for a twodimensional matrix
problem ：
Write an efficient algorithm to judge m x n Matrix , Is there a target value . The matrix has the following characteristics ：
The integers in each row are arranged in ascending order from left to right . The first integer in each row is greater than the last integer in the previous row .
Example ：
Input ：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output ：true
Input ：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output ：false
Copy code
Ideas ：
Ordered array , Look for elements , I've done a few questions . It's not easy .
But it's a twodimensional array , There are two ways to solve the problem .
Mode one
Because the title means , The first number in each line is greater than the last number in the previous line . This will directly link the beginning and end of each line , Is a complete and orderly data . Then the direct basic dichotomy is used to solve .
Mode two
First column , It must be the smallest number in this line . So let's find the first column , Find the last one less than or equal to the target value . Deformation of binary search , That's OK . Then the target value can only appear on that line , Just do a binary search on the data in that row .
such as ： We are looking for 17.
First find the last row less than or equal to the target value for the first column . That's the second line [10,11,16,20], And then look in two .so easy
Code ：
Mode one
In fact, we don't really have to create an array , Splice the first and last lines together . In fact, as long as we can access the corresponding elements according to the array subscript .
mn Matrix , The interval of all elements is 0～mn1.
 Divide the subscript by the number of each line , Round down to know the number of lines
 Remainder subscript , You know the number of elements in the current line
var searchMatrix = function (matrix, target) {
// Put each line together （ Splice the beginning of the next line and the end of the previous line ）, Form an ordered array
function bsearch(left, right) {
while (left <= right) {
let mid = left + Math.floor((right  left) / 2)
// Note that there mid How to get the corresponding element
let x = Math.floor(mid / matrix[0].length)
let y = mid % matrix[0].length
let element = matrix[x][y]
// 
if (element === target) return true
if (element > target) {
right = mid  1
}
if (element < target) {
left = mid + 1
}
}
return false
}
// Pass on
return bsearch(0, matrix.length * matrix[0].length 1)
};
Copy code
Mode two
var searchMatrix = function (matrix, target) {
function bsearch(left, right, sign, index) {
while (left <= right) {
let mid = left + Math.floor((right  left) / 2)
let element = sign === 'row' ? matrix[index][mid] : matrix[mid][index]
if (element === target) return true
if (element > target) {
right = mid  1
}
if (element < target) {
if (sign === 'column' && (mid === matrix.length  1  matrix[mid + 1][0] > target)) {
return mid
}
left = mid + 1
}
}
return false
}
// First find the first column , The last is less than or equal to the value of the specified element index
const columnIndex = bsearch(0, matrix.length  1, 'column', 0)
if (typeof columnIndex === 'boolean') return columnIndex
// Then find that line , Do a binary search on that line
if (columnIndex > 1) {
return bsearch(0, matrix[columnIndex].length  1, 'row', columnIndex)
} else return false
};
Copy code
4. Find the median of two positive arrays
Here comes the key question ,hard You can still try .
problem ：
Given two sizes, they are m and n Positive order of （ From small to large ） Array nums1 and nums2. Please find and return the values of these two positive ordered arrays Median .
Tips ： nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 106 <= nums1[i], nums2[i] <= 106 Advanced ： You can design a time complexity of O(log (m+n)) Does the algorithm solve this problem ？
Example ：
Input ：nums1 = [1,3], nums2 = [2]
Output ：2.00000
explain ： Merge array = [1,2,3] , Median 2
Input ：nums1 = [1,2], nums2 = [3,4]
Output ：2.50000
explain ： Merge array = [1,2,3,4] , Median (2 + 3) / 2 = 2.5
Input ：nums1 = [0,0], nums2 = [0,0]
Output ：0.00000
Copy code
Ideas ：
We're looking for the median , In fact, just take the element of the subscript of the middle array .
It's just that there are two ordered arrays , There is no synthetic .
Subject requirements O(log (m+n)) The algorithm of , I don't think much . Heap sort , Merge sort ,
Heap sorting is obviously not suitable for , Merge and sort ？ In fact, there is no need to merge and sort here , Directly traverse the array and merge . Strictly speaking, time complexity O(m+n) 了 . It doesn't quite meet the requirements of the topic .
accord with O(log (m+n)) The algorithm of , Two points must be considered . You can use the idea of dichotomy , Find the elements . Until the desired subscript element is found . For example, the length of two numbers is m+n, The middle number is k Elements .
Then we have to find The smallest is k Elements , The smallest is k Elements ！
Dichotomy joins
We find half of each array at a time , Then the first time we look for k Just the smallest element .
Let's split it into two arrays , Find each array k/2 individual . be A[k/2  1] Namely A Array find k/2 The largest of the elements , Because arrays are ordered .
B[k/2 1] Namely B Array to find the largest .
Both arrays have been found . What's going on , How do we determine which numbers are the smallest 0～k A? ？
Just better than their maximum
The two biggest contrasts .A[k/2  1] and B[k/2 1] contrast ,

If a>=b,
That's for sure B[0]~B[k/2 1] These figures must be in the range . that B[0]~B[k/2 1] These figures have been found . I have found k/2 Elements , The biggest one is B[k/2 1]. 
If b>a,
That's it A[0]~A[k/2 1] These numbers find , The biggest thing is A[k/2 1].
Then mark A Array found k/2 Or B Array found K/2 individual . Next time, look directly at the mark
Continue to look for... In the next round , How many numbers are we looking for ？kk/2 = k/2.
Just continue to split into two arrays , Everyone needs to find k/4 Elements come out , Take the biggest comparison .
Until the second k An element or k1 Find an element . We'll know the middle number .
drawing , Walk from the beginning ！！
The premise is that the two arrays are ordered , In ascending order A:[1,2,3,4,5] B:[2,3,4]

Altogether 8 Elements , The middle number is 4、 The first 5 Number . that k=5

Two arrays find k/2 ~= 2 Comparison of elements

Compare to find the last element ,3>2, therefore A The two elements found must be ok , They are all the smallest k Before the elements . This time mark a1=2, Record again that the largest element currently found is pastMax=2, Because the largest element found each time , You have to compare the relationship with the largest element collected , Just know who's last , So the collected element is equal to k or k1 when , You will know the specific value of the element .

Go on to the next round , We need to find k2=3, Then spread it equally to two arrays , Each array needs to look back for an element .

3>2, that B Array found a small element ,b1=1, Before maxpast=2, The element found now is also 2, It doesn't matter who is in front of or behind . At this time... Has been collected 3 A digital [1,2,2]

The next round of , We need to find k3=2, Then each array continues to find an element .

3>=3, Then we choose to add the elements of one of the arrays to the collected , Just add B Okay . be b1=2,pastMax Yi Zhuwei 3. here , We have found 4 Elements pull ！！, The first 4 A small element is just pastMax, It is currently found 4 Maximum number of elements , Of course that's the second 4 A small element .

The next round of ,k22=1. In this case , It should also be one for each array to compare , The small one is the element we want to find . But in special cases, one of the arrays has been searched . Let's take A Just the next element of the array . That's it 3

return (3+3)/2 = 3
var findMedianSortedArrays = function (nums1, nums2) {
let finnal = Math.floor((nums1.length + nums2.length) / 2) + 1
let point1 = 0
let point2 = 0
let pastMax = Infinity
const res = []
while (finnal > 0) {
let half = Math.max(Math.floor(finnal / 2), 1)
let num1, num2
// Boundary situation , The length of the number to be found later exceeds the length of the array
let more1 = Math.min(half, nums1.length  point1)
num1 = nums1[point1 + more1  1]
let more2 = Math.min(half, nums2.length  point2)
num2 = nums2[point2 + more2  1]
// Boundary situation , One of the arrays has been found .
if (nums1.length === point1) {
// ～～～ It's special here , If one of them is finished , You can't directly take the elements of another array , Want to be with pastMax contrast
// Who is the biggest element found so far
if (finnal > 2 && nums2[point2 + finnal  2] >= pastMax) {
res.push(nums2[point2 + finnal  2], nums2[point2 + finnal  1])
break
}
num1 = Infinity
}
if (nums2.length === point2) {
if (finnal > 2 && nums1[point1 + finnal  2] >= pastMax) {
res.push(nums1[point1 + finnal  2], nums1[point1 + finnal  1])
break
}
num2 = Infinity
}
if (num1 >= num2) {
point2 += more2
finnal = more2
pastMax = Math.max(num2, pastMax)
} else {
point1 += more1
finnal = more1
pastMax = Math.max(num1, pastMax)
}
if (finnal === 1  finnal === 0) {
res.push(pastMax)
}
}
if ((nums1.length + nums2.length) % 2 === 0) {
return (res[0] + res[1]) / 2
} else {
return res[1]  res[0]
}
};
Copy code