704 binary search

Given an ordered (ascending) integer array nums with n elements and a target value, write a function to search for target in NUMs, returning a subscript if the target value exists, and -1 otherwise.

Example 1: Input nums = [-1,0,3,5,9,12], target = 9 Output: 4 Example 2: Input nums = [-1,0,3,5,9,12], target = 2 Output: -1Copy the code

Link: leetcode-cn.com/problems/bi…

Their thinking

The brute force solution would be to start over the array, but since the array is ordered, it can be optimized for binary search. Start in the middle and search to the left or right depending on the size of the result.

Mid = floor((left+right)/2); left<=right; mid = floor((left+right)/2); ,

The time is order logn.

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var search = function(nums, target) {
    let right = nums.length - 1;
    let left = 0;
    while(left <= right){
        let mid = Math.floor((right + left) / 2);
        if(nums[mid] === target)
            return mid;
        if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1; }}return -1;
};
Copy the code

69 square root of x

Implement the int SQRT (int x) function. Calculates and returns 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 fractional part is omitted.

Example 1: Input: 4 Output: 2 Example 2: Input: 8 Output: 2 Description: The square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

Their thinking

So if you just enumerate all the numbers from 1 to x, and see if the squares are the same as x. As above, binary search can be optimized because it is ordered.

The easy thing to miss about this problem is that if it’s not exactly equal, we’re going to return the largest integer smaller than SQRT (x), so if we get mid * mid < x, we’re going to update res, and we’re definitely going to look right. If we keep looking, we’re going to increase res, So you end up with res.

/ * * *@param {number} x
 * @return {number}* /
var mySqrt = function(x) {
    if(x === 0)
        return 0;
    if(x === 1)
        return 1;
    let left = 0;
    let right = x;
    let res = -1;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        //let mid = (left + right) >> 1; You can also use shift
        let sum = mid * mid;
        if(sum === x)
            return mid;
        if(sum > x){
            right = mid - 1;
        }else{
            res = mid;
            left = mid + 1; }}return res;
    
};
Copy the code

50Pow(x, n)

Implement POW (x, n), that is, compute x to the NTH power function.

Example 1: Input x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input x = 2.10000, n = 3 Output: 9.26100 Example 3: input x = 2.00000, n = -2 Output: 2-2 = 1/22 = 1/4 = 0.25Copy the code

Link: leetcode-cn.com/problems/po…

1

Brute force, but it runs out of time

/ * * *@param {number} x
 * @param {number} n
 * @return {number}* /
let myPow = function(x, n) {
    if(x === 0)
        return 0;
    if(n === 0)
        return 1;
    let sum = 1;
    let mi = n > 0 ? n : -n;
    while(mi--){
        sum *= x;
    }
    if(n > 0) {return sum;
    }else{
        return 1/ sum; }};Copy the code

2

Quick power method: for positive numbers, x ^ n = (x * x) ^ (n / 2) if n is even, and x ^ n = x * x ^ (n-1) if n is odd.

/ * * *@param {number} x
 * @param {number} n
 * @return {number}* /
let myPow = function(x, n)  {
    if(n === 0)
        return 1;
    if(n === 1)
        return x;
    let abs = Math.abs(n);
    letisMinus = n ! == abs;let sum = abs % 2 ? x * myPow(x,abs-1): myPow(x*x, abs/2);
    return isMinus ? 1 / sum : sum;

};
Copy the code