In mathematics and computer science, a well-defined sequence of specific steps of computation, often used in computation, data processing, and automatic reasoning. To be precise, the algorithm is an efficient way to represent a finitely long list. The algorithm should contain clearly defined instructions for calculating the function. – From Wikipedia

Writing in the front

Algorithms may not seem very close to our average developer, but they are actually very relevant to our development. Different algorithms may perform the same task with different time, space, or efficiency. The advantages and disadvantages of an algorithm can be measured by space complexity and time complexity. I regret that I didn’t learn algorithms and data structures well in college. This article is a simple understanding of the algorithm, not an in-depth discussion. After all, each in-depth discussion is enough to drink a pot. Just to understand the thinking and implementation of the algorithm. After all, September is a prime month for job-hopping, so who knows?

In my opinion, the most intuitive role of algorithms is to strengthen our programming thinking logic. Let us develop the mindset to solve problems in simple ways. So let’s get into the algorithm. The relevant examples mentioned in this article are relatively simple. Most of it comes from the Leetcode array section. The code is all my own implementation, not necessarily the optimal solution. Welcome to submit a better way of implementation in the issue. Parsing is written in code comments.

To avoid unnecessary errors, the examples in this article are written in Typescript, the JavaScript code is here, and the article is divided into two main sections, LeetCode/ Simple algorithms

Leetcode part

1: deletes duplicates in the sorted array

Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

Given the array nums = [1,1,2], the function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. You don’t need to worry about the element after the new length in the array.

Given a sorted array, you need to remove duplicate elements in place, so that each element appears only once, and return the new length of the removed array. * Do not use extra array space, you must modify the input array in place and do so with O(1) extra space. Given the array nums = [1,1,2], the function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. * You do not need to consider elements after the new length in the array. * /
const removeDuplicates =  function(nums: number[]) :number {
  let i: number = 0
  for (let j = 0; j < nums.length; j++) {
    if(nums[j] ! == nums[i]) { i++ nums[i] = nums[j] } } nums.splice(i+1)
  console.log(nums)
  console.log(nums.length)
  return i + 1
}
Nums [I]nums[I]nums[j]≠nums[I] * Therefore we must copy the value of it (nums[j]nums[j]) to nums[I +1] nums[I +1]. Then increment II, and we repeat the same process again until JJ reaches the end of the array. * Complexity analysis: * Time complexity: O(n) Assuming the array length is N then I and j are traversed at most n steps * space complexity: O(1) */
removeDuplicates([0.0.1.1.1.2.2.3.3.4])
Copy the code

2: The best time to buy and sell stocks

Given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

The sample

Input:,1,5,3,6,4 [7]

Output: 7

Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.

/** * 2: The best time to buy and sell stocks * Given an array, its ith element is the price of a given stock on the ith day. * Design an algorithm to calculate the maximum profit you can make. You can complete up to one trade * Note: You cannot participate in multiple trades at the same time (you must sell the previous stock before buying again) * * Input: [7,1,5,3,6,4] * Output: 7 * Explanation: By buying on day 2 (stock price = 1) and selling on day 3 (stock price = 5), the exchange makes a profit of 5-1 = 4. * Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3. * /
 // The first way
const maxProfit = function (prices: number[]) :number {
  if(prices.length < 2) return 0
  // Define profit
  let count: number = 0
  let PreMin:number =prices[0]
  // Get the maximum profit per day
  for (let i = 0; i < prices.length; i++) {
    count = Math.max(count, prices[i] - PreMin)
    PreMin = Math.min(PreMin, prices[i])
  }
  console.log(count)
  return count
}
/** * parsing: greedy algorithm */
console.log('= = = = = = = = = = = = = = = = = best buy stock timing greedy algorithm is = = = = = = = = = = = = = = = = = = =');
console.log(maxProfit([7.1.5.3.6.4]));
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');

// The second way is simpler
const maxProfitMore = function (prices: number[]) :number{
  if(prices.length < 2) return 0
  let ret = 0
  for (let i = 0; i < prices.length; i++) {
    // If the next day's price is greater than that of the day, then the profit is calculated
    if (prices[i+1] > prices[i]) {
         ret += prices[i+1] - prices[i]
    }
  }
  return ret
}
As long as the price of the next day is greater than the price of today, we sell. The end result of the current day is our total profit */
console.log('= = = = = = = = = = = = = = = = = = best buy stock time not greed algorithm = = = = = = = = = = = = = = = = = =');
console.log(maxProfitMore([7.1.5.8.3.6.4]))
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

3: Rotates the array

Given an array, move the elements of the array k positions to the right, where k is non-negative.

Example inputs: [1,2,3,4,5,6,7] and k = 3

Output:,6,7,1,2,3,4 [5]

Explanation:

Rotate 1 step to the right: [7,1,2,3,4,5,6]

Rotate 2 steps to the right: [6,7,1,2,3,4,5]

Rotate 3 steps to the right: [5,6,7,1,2,3,4]

requirements

The in situ algorithm with space complexity O(1) is required.

/** * 3: Given an array, move the elements of the array to the right by k, where k is non-negative. * Requires O(1) space complexity to operate on the original array */
const rotate = function(nums: number[], k: number) {
  // loop k, by which we can determine the number of moves needed
  for (let i = 0; i < k; i++) {
    // Insert in front where we need to move
    nums.unshift(nums[nums.length - 1 - i])
  }
  // Finally, let's deal with our array
  nums.splice(nums.length - k, k)
}
rotate([1.2.3.4.5.6.7].3)
Copy the code

4: There is duplication

Given an array of integers, determine whether there are duplicate elements. The function returns true if any value appears in the array at least twice. Return false if each element in the array is different.

Example input: [1,2,3,1] output: true

/** * 4: duplicate elements given an array of integers, check whether there are duplicate elements. * The function returns true if any value appears in the array at least twice. Return false if each element in the array is different. * * this is definitely not optimal */
const containsDuplicate = function (nums: number[]) :boolean{
    / / set the flag
    let judge = false
    // error tolerance
    if (nums.length <= 1) {
      return judge
    }
    // Through the simplest straightforward ideas to deal with the heavy
    let current :number[] = []for (let i = 0; i < nums.length; i++) {
      if (current.indexOf(nums[i]) === - 1) {
        current.push(nums[i])
      } else {
        return judge = true}}return judge
}
console.log('================ is there a duplicate algorithm ====================');
console.log(containsDuplicate([3.1]))
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
// This is actually a very common and simple algorithm but needs to take into account a little more
Copy the code

5: a number that appears only once

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

The sample

Input: [2, 2, 1]

Output: 1.

It requires that your algorithm should have linear time complexity. Additional space does not apply to this implementation

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once. * Your algorithm should have linear time complexity. No extra space is used to implement */
const singleNumber = function(nums: number[]) :number {
  let index= - 1
  // The purpose of the double-level comparison is to compare the current key with each key in the array
  nums.forEach((key, j) = > {
    // loop small cursor each time
    let count = 0
    for (let k = 0; k < nums.length; k++) {
      if (key === nums[k]) {
        count += 1
      }
      // find the subscript that matches the condition
      if (k === nums.length - 1 && count === 1) {
        index = j
      }
    }
  })
  return nums[index]
}
console.log('================= Search single number algorithm ===================');
console.log(singleNumber([2.2.1.3.3]))
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

6: Intersection of two arrays

Given two arrays, write a function to calculate their intersection.

The sample

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2]

requirements

• The number of occurrences of each element in the output should be the same as the number of occurrences of the element in both arrays.
• We can ignore the order of the output.

/** * 6: Find the intersection of two arrays */
const intersect = function (nums1:number[], nums2:number[]) :number[]{
  let arr:number[] = []
  for (let i = 0; i < nums1.length; i++) {
    if(nums2.indexOf(nums1[i]) ! = =- 1 ) {
      nums2.splice(nums2.indexOf(nums1[i]), 1)
      arr.push(nums1[i])
    }
  }
  return arr
}
/** * parsing: in the process of finding the intersection. The main idea is about what an intersection is. * The overlap of two arrays is theoretically the intersection of one array, nums1, and the other array, nums2, are then checked to see if they are present, and if so, nums2 is deleted */
intersect([1.2.2.1], [2.2])
Copy the code

7:1

Given a non-negative integer represented by a non-empty array of integers, add one to that number. You can assume that this integer does not start with zero, except for the integer 0.

The sample

Input: [1, 2, 3]

Output: 4-trichlorobenzene [1]

/** * 7: increments 1 * Given a non-negative integer represented by a non-empty array of integers, increments one to that number. * You can assume that this integer will not start with zero, except for the integer 0. * /
const plusOne =function (nums: number[]) :number[] {
  let j = nums.length - 1
  // js cannot properly represent integers larger than 16 bits.
  for (let i = nums.length - 1; i >=0; i--) {
    // Start adding one by one
    if(i == j) {
      // The value is greater than 10
      if(nums[i] + 1> =10){
        nums[i] = nums[i] + 1 - 10
        j--
        // Last loop
        if (i === 0) {
          nums.unshift(1)}}else {
        nums[j] ++
      }
    } else {
      break}}console.log(nums)
  return nums
}
/ * * * resolution: if you use too large number to digital plus 1 is not enough, we need the operations of a single data, is used in the same operations based on auxiliary cursor * auxiliary cursor j's main function is to record the location of need + 1, if the current is not equal to subscript j then jumped out of the loop: at the same time also improves performance * /
console.log('================ + 1 algorithm ====================');
console.log(plusOne([8.2.1.1.2.2.2.3.5.5.5.5.5.2.3.4.2.3.4.5.5.5.5.2.9]))
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

8: Move zero

Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.

The sample

Input:,1,0,3,12 [0]

Output:,3,12,0,0 [1]

requirements

• Must operate on the original array, cannot copy additional arrays.
• Minimize the number of operations.

Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements. * /
const moveZeroes = function(nums: number[]) {
  // Number of occurrences of 0
  let j = 0
  nums.forEach((el: number, index: number, arr: number[]) = > {
    if (nums[j] === 0) {
      nums.splice(j, 1)
      nums.push(0)}else {
      j++ 
    }
  })
  console.log(nums)
}
/** * new cursor j is used to identify the place where 0 appears. After each move, the cursor will not change, because the original array has been modified, so we need to fix the cursor
console.log('================== Moving zero algorithm ==================');
moveZeroes([1.2.0.0.0.1])
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

9: the sum of two numbers

Given an array of integers and a target value, find two numbers that neutralize the target value in the array. You can assume that there is only one answer for each input and that the same elements cannot be reused.

The sample

Given nums = [2, 7, 11, 15], target = 9

Because nums[0] + NUMs [1] = 2 + 7 = 9

So return [0, 1]

* @param nums * @param target */
const twoSumA = function (nums: number[], target: number) :number[] {
  console.log('Sum of two numbers first solution')
  let arr = [0.0] ,flag = false
  for (let i = 0; i < nums.length; i++) {
    compare(i)
    if (flag) {
      arr = [i, compare(i)]
      break}}/** * @param num */
  function compare(index: number) :number {
    for (let j = 0; j < nums.length; j++) {
      if(j! == index && nums[index] + nums[j] === target) { flag =true
        return j
      }
    }
  }
  return arr
}
/** * second solution */
const twoSumB = function (nums: number[], target: number) :number[] {
  let arr = [0.0]
  console.log('Second solution to sum of two numbers')
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if(j! == i && nums[i] + nums[j] === target) {return arr = [i,j]
      }
    }
  }
  return arr
}
// When comparing two numbers in an array, be sure to exclude yourself from adding them.
console.log('================= Sum of two numbers algorithm ===================');
console.log(twoSumA([3.2.4].6))
console.log(twoSumB([2.7.11.15].9))
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

10: Valid Sudoku

Determine if a 9×9 sudoku is valid. You only need to verify that the numbers you have entered are valid according to the following rules.

1. The numbers 1-9 can appear only once in each line.
2. The numbers 1-9 May appear only once in each column.
3. The numbers 1-9 can occur only once in each 3×3 palace separated by a thick solid line.

The sample

For a given

[["5"."3"."."."."."Seven"."."."."."."."."],
  ["6"."."."."."1"."9"."5"."."."."."."],
  ["."."9"."8"."."."."."."."."."6"."."],
  ["8"."."."."."."."6"."."."."."."."3"],
  ["4"."."."."."8"."."."3"."."."."."1"],
  ["Seven"."."."."."."."2"."."."."."."."6"],
  ["."."6"."."."."."."."."."2"."8"."."],
  ["."."."."."."4"."1"."9"."."."."."5"],
  ["."."."."."."."."8"."."."."."Seven"."9"]]Copy the code

Output js true

instructions

• A valid sudoku (partially filled) is not necessarily solvable.
• You only need to verify that the entered numbers are valid according to the above rules.
• Given sudoku sequences contain only the numbers 1-9 and the characters ‘.’.
• Sudoku is always 9×9.

/** * 10: valid sudoku */
let board = / * [[" 5 ", "3", ""," ", "7", ""," ", ""," "], [" 6 ", ""," ", "1", "9", "5", ""," ", ""]. [". ", "9", "eight" and ". ", ""," ", ""," 6 ", ""], [" 8", ""," ", ""," 6 ", ""," ", ""," 3 "], [" 4 ", ""," ", "eight" and ". ", "3", ""," ", "1"]. [" 7 ", ". ", ""," ", "2", ""," ", ""," 6 "], [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"]. [". ", ". ", ""," ", "eight" and ". ", ""," 7 ", "9"]] * /
[["Seven"."."."."."."."4"."."."."."."."."],
 ["."."."."."."8"."6"."5"."."."."."."],
 ["."."1"."."."2"."."."."."."."."."."],
 ["."."."."."."."."."."9"."."."."."."],
 ["."."."."."."."."5"."."."5"."."."."],
 ["."."."."."."."."."."."."."."."."."],
 ["."."."."."."."."."."."."2"."."."."],
 ["."."."."."."."."."."."."."."."."."],
 ["."."."."."."."."."."."."."."."."."]]const isValidSudoku = function (board: string[] []) :boolean {
  let isPass = true
  const sudokuDeep = 9 // Sudoku depth
  // Determine rows and columns
  for (let i = 0; i < sudokuDeep; i++) {
    let row:any = {}
    let col:any = {}
    for (let j = 0; j < sudokuDeep; j++) {
      / / line
      /**
       * 判断方式
       * 首先判断不为'.' => 然后判断是否存在row对象中 
       */
      if(board[i][j] ! = ='. ') {
        if (row[board[i][j]]) {
          console.log(board[i][j])
          return isPass = false
        } else {
          row[board[i][j]] = board[i][j]
        }
      }
      / / judgment
      if(board[j][i] ! = ='. ') {
        if (col[board[j][i]]) {
          console.log(board[j][i]);
          return isPass = false
        } else {
          col[board[j][i]] = board[j][i]
        }
      }
      // Use the remainder to determine the number of squares you are in
      // Calculate the position first
      let c = Math.floor(i/3)  / / col location
      let r = Math.floor(j/3) / / row position
      // Outline the nine squares
      for (let m = c*3; m < c*3 + 3; m++) {
        for (let n = r * 3; n < r * 3 + 3; n++) {
          if (m === i && n === j) {
            // m === I &&n === j then point to the same position
            continue
          } else {
            // The most important evaluation judgment
            if(board[m][n] ! ='. '&& board[i][j]! = ='. ' && (board[i][j]) === board[m][n]) {
              return isPass = false
            } 
          }
        }
      }
      
    }
  }
  return isPass
}
console.log('================= Results of valid Sudoku algorithm ===================');
console.log(isValidSudoku(board))
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

11: Rotate the image

Given an n by n two-dimensional matrix representing an image. Rotate the image 90 degrees clockwise.

The sample

For a given

[[1.2.3],
  [4.5.6],
  [7.8.9]],Copy the code

The output

[[7.4.1],
  [8.5.2],
  [9.6.3]]Copy the code

requirements

You have to rotate the image in place, which means you need to modify the input two-dimensional matrix directly. Please do not use another matrix to rotate the image.

/** * 11: Rotate the image **/
const matrix = [
  [1.2.3],
  [4.5.6],
  [7.8.9]]// 
/ * const matrix = [[5, 1, 9, 10], [2, 4, 8, 10], [13, 3, 6, 7], [15,14,12,16]] * /
const rotateMaps = function (matrix:number[] []) {
  const n = matrix.length
  // Reverse the loop by 90 degrees
  for (let i = n- 1; i >= 0; i--) {
    // The new array is added to the original array, in order to implement the rotation operation in place, if not required
    for (let j = 0; j < n ; j++) {
      // console.log(' current coordinates [${I},${j}] ')
      const current = matrix[i][j]
      matrix[j].push(current)
      // Delete the pre-rotation array before completing the assignment
      if(j === n - 1) {
        matrix[i].splice(0, n)
      }
    }
  }
  console.log(matrix)
  // return matrix
}

console.log('================ Image rotation algorithm ====================');
console.log(rotateMaps(matrix));
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

Other parts (continuously updated…)

This section will start with the demo, and parsing comments will be added later in the code

12: Searches for the parent node

Fid = 0 and CID = 2 and so on…

/** * 10: select parent node * fid = 1, fid = 1, cid = 1, fid = 2, and so on. * /
const findArr = [
  {"fid":0."cid":3."flag":"Outermost shell 3"},
  {"fid":0."cid":4."flag":"Outermost four"},
  {"fid":4."cid":5."flag":Outermost shell -4},
  {"fid":5."cid":6."flag":"Outermost layer -4-1"},
  {"fid":0."cid":7."flag":Outermost shell seven},
  {"fid":7."cid":8."flag":Outermost shell -7},
  {"fid":0."cid":9."flag":"Outermost nine"},
  {"fid":9."cid":10."flag":"Outermost 9-1"},
  {"fid":9."cid":11."flag":"Outermost nine minus two."},
  {"fid":11."cid":12."flag":"Outermost 9-2-1"}]/** * the first method is double recursive * @param arr */
const findfid  = function (arr: any[]) :any[] {
  let newArr:any[] = []
  for (let i = 0; i < arr.length; i++) {
    let flagId = arr[i].cid // Retrieve a flag that is used to match the next level
    for (let j = 0; j < arr.length; j++) {
      const elJ = arr[j]
      if (elJ.fid === flagId) { // FID matches the parent ID
        (arr[i].children = []).push(elJ)
      }
    }
    // Store only the first level
    arr[i].fid === 0 && newArr.push(arr[i])
  }
  return newArr
}
/** * second method: use the object store ID and compare it with FID * @param arr */
const findfidByObj = function (arr: any[]) :any[] {
  let newArr:any[] = []
  let flagObj: any = {}
  arr.forEach(v= > {
    flagObj[v.cid] = v
  })
  arr.forEach (item= > {
    // Based on the FID of the current traversal object, go to the map object to find the corresponding index ID
    const top = flagObj[item.fid]
    if (top) {
      // If the index is found, then the item is not in the top level, so it needs to be added to its parent
      (top.children || (top.children = [])).push(item)
    } else {
      // If no index ID is found in the map, add the current item directly to the newData result set as the top level
      newArr.push(item)
    }
  })
  return newArr
}
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
console.log('Find father node method');
console.log(findfid(findArr))
console.log(findfidByObj(findArr))
console.log('= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =');
Copy the code

13: Simple selection sort

Selection sort is a simple and intuitive sorting algorithm. It works by selecting the smallest (or largest) element from the data elements to be sorted and storing it at the beginning of the sequence until all the data elements to be sorted are sorted. Selection sort is an unstable sort method.

/ * * * * @ param exchange parameters {*} arr * @ param} {* a * @ param} {* b * /
const swap = function(arr: number[], a:number, b:number) {
  let curr = arr[a]
  arr[a] = arr[b]
  arr[b] = curr
}
/** ** @param {select sorting algorithm} arr */
const sort = function (arr: number[]) {
  console.time()
  for (let i = 0; i < arr.length; i++) {
    // Assume that the current first traversal is the smallest
    let minIndex = i
    Arr [minIndex] and other values in the array
    for (let j = 0; j < arr.length; j++) {
      if(arr[minIndex] > arr[j]){
        minIndex = j
      }
    }
    // The outer loop does the swap
    swap(arr,minIndex,i)
  }
  console.log(arr)
  console.timeEnd()
}
sort([3.6.28.123.34])
Copy the code

14: Simple bubble sort

Bubble Sort is a simple sorting algorithm in the field of computer science. It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if they are in the wrong order (from largest to smallest, from A to Z). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element has been sorted.

/** * @param {* bubble sort algorithm} arr */
const bubbleSort = function (arr: number[]){
  console.log('Bubble algorithm start time :')
  console.time()
  for (let i = 0; i < arr.length; i++) {
    // This loop gets the following items for comparison
    for (let j = i+1; j > 0; j--) {
      // The core is that if the current item is smaller than the previous item, the current item bubbles up
      if(arr[i] < arr[j- 1]) {// Bubble swap
        swap(arr,j,j- 1)}}}console.timeEnd()
  console.log(arr)
}
bubbleSort([3.123.6.28.34])
Copy the code

15: Simple insertion sort

Insertion sort is sort based on comparison. The so-called comparison-based method is to compare the elements in an array to see which ones are larger and which ones are smaller, and adjust the positions of the elements based on the results.

// Insert sort algorithm
/** ** @param {insert sort} arr */
const insertSort = function (arr: number[]){
  console.time()
  for (let i = 0; i < arr.length; i++) {
    // The current value is first cached in a loop and compared to the previous index
    let compareIndex = i - 1
    let currentValue = arr[i]
    // Insert the cached value when the current position is comparable and the current value is less than the previous value and then modify index
    while (compareIndex >=0 && arr[compareIndex] > currentValue) {
      arr[compareIndex + 1] = arr[compareIndex]
      compareIndex--
    }
    arr[compareIndex + 1 ] = currentValue
  }
  console.timeEnd()
  console.log(arr)
}
insertSort([3.2.1])
Copy the code

16: simple binary search algorithm

Binary search is also called split search. Retrieves a specified value in an ordered array and returns the index of that value in the array.

/** * binary search algorithm * what is binary search? Binary search is also called split search. Retrieves a specified value in an ordered array and returns the index of that value in the array. * (1) The search starts at the middle element of the ordered array, and if that element happens to be the specified value, the search process ends. Otherwise proceed to the next step; * (2) If you specify that the element to be searched is greater than or less than the middle element, search the half of the array that is greater than or less than the middle element, and then repeat the operation of the first step; * (3) Repeat the above process until the index of the target element is found and the search is successful; Or until the subarray is empty, the search fails. * Note: this first to sort the array in the ordered array search * advantage is less comparison times, fast search, good average performance; * The disadvantage is that the table to be looked up is ordered, and it is difficult to insert and delete. Therefore, the split search method is suitable for frequent ordered lists that do not change often. * /
/ non-recursive implementation * * * * @ param {*} arr * @ param target * / {*}
function binarySearcNoRecursive(arr: number[], target: number){
  let low: number = 0, high: number = arr.length- 1
  while(low <= high) {
    // Find the middle position first
    let middle = ((high + low ) / 2)
    if( target === arr[middle]){
      return middle
    } else if (target > arr[middle]){
      low = middle + 1
    } else if ( target < arr[middle] ){
      high = middle - 1
    }else { 
      return - 1}}}const result = binarySearcNoRecursive( [1.2.3.4.5.6.7.8.9.10.11.23.44.86].23)
console.log('Binary search without a loop to find the location:${result}`)
/** * recursive implementation loop calls itself * @param {*} arr * @param {*} target */
function binarySearcRecursive(arr: number[], low:number, high: number, target:number){
  if(low > high){
    return - 1
  }
  let middle = ((high + low ) / 2)
  if(arr[middle] === target){
    return middle
  } else if(arr[middle] > target){
    high = middle - 1
    binarySearcRecursive(arr, low, high, target)
  } else if(arr[middle] < target){
    low = middle + 1
    binarySearcRecursive(arr, low, high, target)
  }
}
const  recursiveRes = binarySearcNoRecursive( [1.2.3.4.5.6.7.8.9.10.11.23.44.86].3)
console.log('Binary search without a loop to find the location:${recursiveRes}`)
Copy the code

conclusion

Algorithm reprogramming occupies a very important position, language technology can be quickly. But algorithms need a solid foundation of theoretical knowledge. This article is just based on the topic in Leetcode, simple implementation. Feel the magic of algorithms. If you study, I suggest you study systematically and deeply.

The code address

The corresponding JavaScript sample code address

Original address if feel useful words to ⭐ bar