"Search algorithm" of advanced algorithm
1, Theory
1. Introduction to sorting and searching
- Sort: to turn an out of order array into an ascending or descending array
- Search: find the subscript of an element in the array
1.1 sorting and searching in JS
- Sorting in js: sort()
- Search in js: indexOf()
1.2 sorting algorithm
- Bubble sorting
- Select sort
- Insert sort
- Merge sort
- Quick sort
1.3 search algorithm
- Sequential search
- Binary search
2. js realize sorting
2.1 bubble sorting
2.2.1 ideas
- Compare adjacent elements and swap them if the first is larger than the second
- After one round, ensure that the last number is the largest
- The sorting is completed by executing n-1 rounds
2.2.2 animation demonstration
Bubble sorting animation demonstration
2.2.3 coding part
Array.prototype.bubbleSort = function () {
for(let i = 0; i < this.length - 1; i++) {
for(let j = 0; j < this.length - 1 - i; j++) {
if(this[j] > this[j + 1]) {
const temp = this[j]
this[j] = this[j + 1]
this[j + 1] = temp
}
}
}
}
2.2.4 time complexity
- Time complexity: O(n^2)
2.2 selection and sorting
2.2.1 ideas
- Find the minimum value of the array, select it and put it first
- Find the second smallest value of the array, select it and put it in the second place
- And so on, execute n-1 round
2.2.2 animation demonstration
Select sort animation presentation
2.2.3 coding part
Array.prototype.selectionSort = function () {
for(let i = 0; i < this.length-1; i++) {
let indexMin = i
for(let j = i; j < this.length; j++) {
if(this[j] < this[indexMin]) {
indexMin = j
}
}
if(indexMin !== i) {
const temp = this[i]
this[i] = this[indexMin]
this[indexMin] = temp
}
}
}
2.2.4 time complexity
- Time complexity: O(n^2)
2.3 insert sort
2.3.1 ideas
- Start with the second number and move forward
- If you're older than him, go to the back
- And so on to the last number
2.3.2 animation demonstration
2.3.3 coding part
Array.prototype.insertionSort = function () {
for(let i = 1; i < this.length; i++) {
const temp = this[i]
let j = i
while(j > 0) {
if(this[j-1] > temp) {
this[j] = this[j-1]
} else {
break
}
j--
}
this[j] = temp
}
}
2.3.4 time complexity
- Time complexity: O(n^2)
2.4 merge sort
2.4.1 ideas
- Divide: divide the array into two parts, and then recursively "divide" the sub array until it is divided into separate numbers
- Combination: combine the two numbers into an ordered array, and then merge the ordered array until all sub arrays are merged into a complete array
Merge two ordered arrays
- Create an empty array res to store the array after final sorting
- Compare the heads of two ordered arrays, and the smaller one is out of the queue and pushed into res
2.4.2 animation demonstration
Merge sort animation demonstration
2.4.3 coding part
Array.prototype.mergeSort = function () {
const rec = arr => {
if(arr.length == 1) return arr
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, arr.length)
const orderLeft = rec(left)
const orderRight = rec(right)
const res = []
while(orderLeft.length || orderRight.length) {
if(orderLeft.length && orderRight.length) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
} else if(orderLeft.length) {
res.push(orderLeft.shift())
} else if(orderRight.length) {
res.push(orderRight.shift())
}
}
return res
}
const res = rec(this)
res.forEach((n, i) => this[i] = n)
}
2.4.4 time complexity
- Time complexity of minutes: O(logn)
- Combined time complexity: O(n)
- Time complexity: O(nlogn)
2.5 quick sort
2.5.1 ideas
- Partition: select any benchmark from the array. All elements smaller than the benchmark are placed before the benchmark, and the elements smaller than the benchmark are placed after the benchmark
- Recursion: recursively partition subarrays before and after the benchmark
2.5.2 animation demonstration
2.5.3 coding part
Array.prototype.quickSort = function () {
const rec = (arr) => {
if(arr.length == 1) return arr
const left = []
const right = []
const mid = arr[0];
for(let i = 1; i < this.length; i++) {
if(arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...rec(left), mid, ...rec(right)]
}
const res = rec(this)
res.forEach((n, i) => this[i] = n)
}
2.5.4 time complexity
- Recursive time complexity: O(logn)
- Partition time complexity: O(n)
- Time complexity: O(nlogn)
3. js to achieve search
3.1 sequential search
3.1.1 ideas
- Traversal array
- Find the element equal to the target value and return its subscript
- After traversal, if no equivalent element is found, - 1 is returned
3.1.2 coding part
Array.prototype.sequentialSearch = function(item) {
for(let i = 0; i < this.length; i++) {
if(this[i] === item) {
return i
}
}
return -1
}
3.1.3 time complexity
- Time complexity: O(n)
3.2 binary search
Premise: array order
3.2.1 ideas
- Start with the middle element of the array. If the middle element is exactly the target value, the search ends
- If the target value is greater than or less than the intermediate element, search in the half array greater than or less than the intermediate element
3.2.2 coding part
Array.prototype.binarySearch = function(item) {
let low = 0, high = this.length - 1
while(low <= high) {
const mid = Math.floor((low + high) / 2)
const element = this[mid]
if(element < item) {
low = mid + 1
} else if(element > item) {
high = mid - 1
} else {
return mid
}
}
return -1
}
3.2.3 time complexity
- Time complexity: O(logn)
2, Brush questions
1. Merge two ordered linked lists (21)
1.1 Title Description
- Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists
1.2 problem solving ideas
- It is similar to merging two ordered arrays in merge sort
- Replace array with linked list
1.3 problem solving steps
- Create a new linked list as the return result
- Use the pointer to traverse two ordered arrays and compare the current nodes of the two linked lists. The smaller one will access the new linked list first and move the pointer one step later
- After traversing the linked list, a new linked list is returned
function mergeTwoLists(l1, l2) {
const res = new ListNode(0);
let p = res, p1 = l1, p2 = l2;
while(p1 && p2) {
if(p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if(p1) {
p.next = p1;
}
if(p2) {
p.next = p2
}
return res.next
}
1.4 time complexity & space complexity
- Time complexity: O(n)
- Space complexity: O(1)
2. Guess the size of the number (374)
2.1 Title Description
- The rules of the number guessing game are as follows:
- In each round of the game, I will randomly choose a number from # 1 # to # n. Please guess which number you chose.
- If you guess wrong, I'll tell you whether the number you guessed is larger or smaller than the number I chose.
- You can call a predefined interface int guess(int num) to get the guess result. There are three possible return values (- 1, 1 or 0):
- -1: My number is small pick < num
- 1: My number is big pick > num
- 0: Congratulations! Bingo! pick == num
2.2 problem solving ideas
Input: n = 10, pick = 6
Output: 6
- Binary search
- Call the guess function to determine whether the intermediate element is the target value
2.3 problem solving steps
- Binary search
function guessNumber(n) {
let low = 1, high = n;
while(low <= high) {
const mid = Math.floor((low + high) / 2);
const res = guess(mid)
if(res === 0) {
return mid
} else if(res === 1) {
low = mid + 1
} else if(res === -1) {
high = mid - 1
}
}
}
2.4 time complexity & space complexity
- Time complexity: O(logn)
- Space complexity: O(1)