# "Data structure and algorithm" of front end -- binary search

Forrest Gump gk11upup 2021-09-15 09:14:51

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

1. The loop condition
`left <= right`
If it is `left < 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 .
2. Update of interval boundary
left and right Pointer update ,
`right = mid - 1,left = mid + 1`
It may appear that it will be written as `right = 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

## 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`.
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[n-1], nums, nums, ..., nums[k-1]]（ 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 .

1. Divide the array in half
2. Judge whether one group is orderly , Use the basic dichotomy to directly search for elements and return results
3. 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
}
return mySplit(0, nums.length - 1)
};
Copy code ``````

## 74. Search for a two-dimensional 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 two-dimensional 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～mn-1.

• 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.length)
let y = mid % matrix.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.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] > 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 = 
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~B[k/2 -1] These figures must be in the range . that B~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~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 ？k-k/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 k-1 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]` 1. Altogether 8 Elements , The middle number is 4、 The first 5 Number . that k=5

2. Two arrays find k/2 ~= 2 Comparison of elements 3. 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 k-1 when , You will know the specific value of the element . 4. Go on to the next round , We need to find k-2=3, Then spread it equally to two arrays , Each array needs to look back for an element . 5. 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] 6. The next round of , We need to find k-3=2, Then each array continues to find an element . 7. 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 . 8. The next round of ,k-2-2=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

9. 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 + res) / 2
} else {
return res || res
}
};
Copy code ``````