This is the 28th day of my participation in the August Challenge
Binary Search is also called Binary Search, which is a highly efficient Search method.
Binary search idea is very simple, algorithm ideas written below, do not know how to take a look (of course, if it is zero based advice or first go back to see what is binary search, learn to understand and then come back to see), understand do not need to see, test is not ideas, the focus is the application.
First of all, assuming that the elements in the table are arranged in ascending order, compare the keywords recorded in the middle of the table with the search keywords. If the two are equal, the search succeeds. Otherwise, the middle position record is used to divide the table into the front and back two sub-tables. If the key word of the middle position record is greater than the search key word, the former sub-table is further searched; otherwise, the latter sub-table is further searched. Repeat the above process until you find a record that meets the criteria, so that the search succeeds, or until the child table does not exist, at which point the search fails.
What I see is left god’s algorithm class, Left Cheng Yun teacher. In fact, I didn’t understand binary search before, it’s just finding numbers in ordered arrays, it’s faster than sequential search. But after watching The lecture on Left God, we found that binary lookup can be used not only for ordered arrays, but also for unordered arrays in certain cases.
So let’s do a couple of problems. Mention is very simple, the code is very simple, I will not analyze each sentence, you can see from beginning to end to understand the small white level of knowledge.
Apply to an unordered array
Given an unordered array arr, it is known that the values of any two adjacent elements are not the same. Please return any local minimum position. Locally minimal locations are:
- If arr[0]
- If AR [n-1] (the rightmost number of ARr) is less than ARr [n-2], then position n-1 is also the locally smallest position.
- If position I is neither the leftmost nor the rightmost. So as long as arr[I] is less than both the left and right sides of the position (arr[i-1] and arr[I +1]), then position I is also a locally smallest position.
D) to find a local minimum. In other words, you just have to find the minimum of some part. Here are some examples:
| Enter the sample | The output sample |
|---|---|
| ,2,3,1,2,3 [1] | 1 |
| ,2,3,1,2,0 [3] | 0 |
| [6, 2, 3, 5, 2, 3] | 2 (2 to the left of 3) or minus 5 |
| ,4,3,1,0,3 [6] | 0 |
The output of the third sample above depends on your code. That’s output 2, as I’ve written it. Because we’re looking for local minima. When the median is larger than both sides, you can return either side, and I’m going to return the left side by default.
function min(a) {
let length = a.length
if (length === 0) { / / array is empty
return -1
} else {
let low = 0
let high = length - 1
let mid
if(low === high || a[0] < a[1]) {Arr [0]
return 0
}else if (a[length - 1] < a[length - 2]) {
return length - 1
} else {
while (low <= high) { / / dichotomy
mid = Math.floor(low + (high - low) / 2) // round down
if (a[mid] < a[mid + 1] && a[mid] < a[mid - 1]) {
return mid
} else if (a[mid] > a[mid - 1]) {
high = mid - 1
} else {
low = mid + 1
}
}
}
}
}
Copy the codeNote: I used low + (high-low)/2 instead of (low + high)/2 in the code because this prevents overflow if the array is too large.
Application in ordered repeating array
1
Given an ordered array arr and an integer num find the leftmost position in arr where the number num appears.
function find(a, num) {
let res = -1
if (a.length === 0) { // The array is empty
return res
}
let right = a.length - 1
let mid
let left = 0
while (left <= right) {
if (a[0] === num) { //a[0] is the number to find
return res = 0
} else {
while (left <= right) {
mid = Math.floor(left + (right - left) / 2)
if (a[mid] === num && a[mid] > a[mid - 1]) {
res = mid
break // You must write, otherwise the loop is endless
} else if (a[mid] < num) {
left = mid + 1
} else {
right = mid - 1}}return res
}
}
}
Copy the code2
Given an ordered array arr with no repeating elements, find the leftmost position that satisfies the condition arr[I]== I. If the number at all positions does not satisfy the condition, -1 is returned.
function find(arr) {
let res = -1
if (arr.length === 0 || arr[0] > arr[length - 1] || arr[length - 1] < 0) {
Arr [I]= I; arr[I]= I; arr[I]= I
return res
} else {
let left = 0,
right = arr.length - 1,
mid = left + (right - left) / 2
while (left <= right) {
mid = Math.trunc(left + (right - left) / 2)
if (arr[mid] < mid) {
left = ++mid
} else if (arr[mid] > mid) {
right = --mid
} else {
res = mid
right = --mid
}
}
return res
}
}
Copy the codeLoop through the array to find the maximum/median
1
Given an ordered loop array arR, return the minimum value in arR. So an ordered loop array means that whatever is on the left of an ordered array goes to the right, and whatever is on the right goes to the left. For example, arrays 1,2,3,3,4 are ordered loops, as are arrays 4,1,2,3, and 3.
| Enter the sample | The output sample |
|---|---|
| ,1,2,3 0, 1, 1, 1 | 1 (res = 4) |
| 0 | 0 |
| 2,2,2,2,1,2,2,2 | 1 |
function Min(arr) {
// The res is just the index, you don't have to write it.
let res = -1;
if (arr.length === 0) {
return res // The array is empty. To find the failure
} else if (arr.length === 1 || arr[0] < arr[arr.length - 1]) {
// If the first value in the array is less than the last value, it has not been flipped
return arr[0]}else {
let left = 0,
right = arr.length - 1,
mid = 0
while (left <= right) {
mid = Math.trunc(left + (right - left) / 2)
if (left + 1 === right) {
res = arr[left] > arr[right] ? right : left
return arr[res]
} else {
if (arr[left] > arr[mid]) {
right = mid
} else if (arr[mid] > arr[right]) {
left = mid
} else if (arr[left] === arr[mid] && arr[mid] === arr[right]) {
let min = arr[0]
for (let i = 1; i < arr.length; i++) {
// This is in response to input sample 3, traversal search
if (arr[i] < arr[0]) {
res = i
return arr[res]
}
}
}
}
}
}
}
Copy the code2
Same problem. What if you had to find the median?
function Min(arr) {
let res = "Array empty, no median";
let m = Math.trunc(arr.length/2)
var num = function(res){
if (arr.length % 2! = =0) {
res = arr[(res + m) % arr.length]
} else {
num1 = arr[(res + m) % arr.length]
num2 = arr[(res + m -1 ) % arr.length]
res = (num1 + num2) / 2
}
return res
}
if (arr.length === 0) {
return res // The array is empty. To find the failure
} else if (arr.length === 1) { // A value in the array
return arr[0]}else if(arr[0] < arr[arr.length - 1]) {// The first one is less than the last one
return num(0)}else {
let left = 0,
right = arr.length - 1,
mid = 0
while (left <= right) {
mid = Math.trunc(left + (right - left) / 2)
if (left + 1 === right) {
res = num(arr[left] > arr[right] ? right : left)
return res
} else {
if (arr[left] > arr[mid]) {
right = mid
} else if (arr[mid] > arr[right]) {
left = mid
} else if (arr[left] === arr[mid] && arr[mid] === arr[right]) {
let min = arr[0]
for (let i = 1; i < arr.length; i++) {
// This is in response to input sample 3, traversal search
if (arr[i] < arr[0]) {
res = num(a[i])
return arr[res]
}
}
}
}
}
}
}
Copy the codeApplication: faster to find an integer k to the N power.
If the time complexity of multiplying two integers and getting the result is O(1), the process of getting the integer k to the N is k*k*… *k complexity is O(n), please find a way to implement the time complexity is O(logN) method.
This is also using the idea of binary search, although I didn’t see it. But I have to say that the algorithm is profound!!
function calculate(a, b) {
let arr = []
// Convert b to base 2 representation
while(b ! =0) {
arr.push(b % 2)
b = Math.trunc(b / 2)}console.log(arr)
let mul = a
let res
if(arr[0]! = =0){
res = a
}else{
res = 1
}
// How many bits do you have in b
for (let i = 1; i < arr.length; i++) {
mul *= mul
console.log("mul: "+mul)
if (arr[i] === 1) {
res *= mul
console.log(res)
}
}
}
Copy the codeThe title comes from the interview algorithm.