“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Hello, everyone, I am quick frozen fish 🐟, a river front 💦, like the colorful 💐, continuous sand sculpture 🌲, is the good brother of the cold grass of the next door. Welcome to add my wechat: Sudongyuer pull you into the group, discuss together, look forward to growing together with you 🥂.

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

The quality of writing instructions will directly affect the performance of the program, and instructions are composed of data structure and algorithm, so the design of data structure and algorithm basically determines the quality of the final program.

In addition, when reading the source code, the lack of understanding of algorithms and data structures makes it difficult to understand why the author wrote the way he did.

In today’s environment, algorithms have become an indispensable skill for front-end engineers. If we want to move beyond being application engineers writing business code, we need to understand algorithms and data structures.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

What is divide and rule? 😊

  • Divide and conquer isA method of algorithm design.
  • It will be a problempointsInto multiple small questions similar to the original question,Recursive solutionSmall problem, then will resultusAnd solve the original problem.

Scenario 1: Merge sort 🍃

  • Split: Splits an array down the middle.
  • Solution: Merge sort of two subarrays recursively.
  • Merge: Merges ordered subarrays

Scenario 2: Quicksort 🍃

  • Points: select base, divide the array into two subarrays according to the base.
  • Solution: A recursive quicksort of two subarrays.
  • Merge: Merges two subarrays.

Guess the number size – divide and conquer 🦀

The title

374. Guess the number size

Difficulty is simple

The rules of the guessing game are as follows:

  • Every round of the game, I take it from1 到 nPick a number at random. Guess which number you picked.
  • If you’re wrong, I’ll tell you if your guess is bigger or smaller than my pick.

You can get the guess result by calling a predefined interface int guess(int num), which returns three possible values (-1, 1 or 0) :

  • -1: The number I picked is smaller than your guesspick < num
  • 1: The number I picked is bigger than you guessedpick > num
  • 0: The number I picked is the same as your guess. A: congratulations! You guessed it!pick == num

Returns the number I selected.

Example 1:

Input: n = 10, pick = 6 Output: 6Copy the code

Example 2:

Input: n = 1, pick = 1 Output: 1Copy the code

Example 3:

Input: n = 2, pick = 1 Output: 1Copy the code

Example 4:

Input: n = 2, pick = 2 Output: 2Copy the code

Tip:

  • 1 <= n <= 231 - 1
  • 1 <= pick <= n

Their thinking

  • Binary search also has the characteristics of “division, solution and combination”.
  • Consider opting for the idea of divide and rule

The problem solving steps

Divide: calculates the intermediate elements and splits the array.

Solution: Recursively performs binary search on larger or smaller arrays.

Merge: this step is not required because it is returned when found in the subarray.

The source code

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	            -1 if num is lower than the guess number
 *			             1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */

/ * * *@param {number} n
 * @return {number}* /
var guessNumber = function(n) {
   const rec=(low,higher) = >{
        if(low>=higher){
           return low
       }
       const mid=Math.floor((low+higher)/2)
       if(guess(mid)===0) {return mid
       }
       else if(guess(mid)===1) {return rec(mid+1,higher)
       }
       else if(guess(mid)===-1) {return rec(low,mid-1)}}return rec(1,n)
};
Copy the code

Conclusion 🌞

The purpose of this article is actually very simple, is to urge myself to complete the algorithm practice and summarize and output, dishes are not important, but love 🔥, I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.

Add me on wechat: Sudongyuer, invite you into the group and learning the front together, become a better engineer ~ (group of qr code here – > front to go to bed early, qr code has expired, see the links to the boiling point in the comments, I will put the latest qr code in the comments section, of course, can also add me WeChat I pull you into the group, after all, I also am interesting front end, I also not bad 🌟 ~