This is the 7th day of my participation in Gwen Challenge

preface

Public number to nPY front-end secrets

Add vx👉16639199716, pull you into the group ao ~❤️

Today we will continue to learn LeetCode’s selected interview questions. Today we choose question 69 to learn and summarize ~

Topic describes

Implement the int SQRT (int x) function to compute and return the square root of x, where x is a non-negative integer

Since the return type is an integer, only the integer part of the result is retained, and the decimal part is omitted.

Example 1

Input: 4

Output: 2

Example 2

Input: 8

Output: 2

Description: The square root of 8 is 2.82842… Since the return type is an integer, the fractional part will be omitted.

Their thinking

In fact, the application scenarios of dichotomy are relatively limited. The most obvious characteristics are:

In most cases, the lookup target is monotone (monotonically increasing, monotonically decreasing) with upper and lower boundaries, and it is best to access elements with index subscripts

Basic dichotomy is used

Let’s start with the simplest monotonically increasing array, with the following problem:

Find 4 in [1, 2, 3, 4, 5, 6, 7, 8, 9], return the subscript if it exists, return -1 if it does not exist, require the algorithm complexity O(logn).

The first response to order logn complexity is to use binary search. How do I do that?

function searchNum (target, nums) {
  if(! nums.length)return -1
  let left = 0
  let right = nums.length - 1
  let mid
  while (left <= right) {
      // >> 1 bit operation instead of division by 2
      // Mid = (left+right)/2
      mid = left + ((right - left) >> 1)
      if (nums[mid] === target) {
          return mid
      }
      if (nums[mid] < target) {
          left = mid + 1
      }
      if (nums[mid] > target) {
          right = mid - 1}}return -1
}
Copy the code

From the above question, we can see the routine of point dichotomy. There are laws to follow, and the basic template can be derived:

let left = start
let right = end
let mid
while (left <= right) {
    mid = (left + right) / 2
    if (array[mid] === target) {
        returnThe result orbreak down
    }
    if (array[mid] < target) {
        left = mid + 1
    }
    if (array[mid] > target) {
        right = mid - 1}}Copy the code

Once we have the basic template for dichotomy, we can then solve the square root of x type problems

const mySqrt = function(x) {
     if (x < 2) return x
     let left = 1, mid, right = Math.floor(x / 2);
     while (left <= right) {
        mid = Math.floor(left + (right - left) / 2)
        if (mid * mid === x) return mid
        if (mid * mid < x) {
            left = mid + 1
        }else {
            right = mid - 1}}return right
}
Copy the code

conclusion

On the 13th day, I chose question 69 and learned how to find the square root of x

❤️ thank you

If you think this content is quite helpful to you: click the like to support it, so that more people can see this content (collection does not like, are playing hoagie – -) pay attention to the public account to NPY front-end secrets, we learn together and progress together. If you feel good, you can also read other articles (thanks to friends for their encouragement and support 🌹🌹🌹)

Start the LeetCode journey

Double pointer to LeetCode

Leet27. Remove elements

Front-end engineers must learn the classic sorting algorithm

LeetCode20. Brackets match

LeetCode7, integer inversion