Array: force deduction dichotomy

course ：https://github.com/youngyangyang04/leetcode-master

Dichotomy

• Time complexity ：O(logx), That is, the number of times needed for binary search .
• Spatial complexity ：O(1).

Newton's iteration

• Time complexity ：O(log x), This method is quadratic convergent , Faster than binary search .
• Spatial complexity ：O(1).
• The formula ：(x+a/x)/2.（ Newton iteration method can be considered when square root is encountered ）

34. Find the first and last positions of the elements in the sort array （ secondary ）

link ：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Title Description ： Given an array of integers in ascending order nums, And a target value target. Find the start and end position of the given target value in the array . If the target value does not exist in the array target, return [-1, -1].

Advanced ：
You can design and implement time complexity of O(log n) Does the algorithm solve this problem ？

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if(len(nums)==0):
            return [-1,-1]
        l , r = 0, len(nums)-1
        left = right = -1
        while(l <= r):
            m = l + (r - l) // 2
            if(nums[m] == target):
                left = right = m
                break
            if(nums[m] < target):
                l = m + 1
            if(nums[m] > target):
                r = m - 1
        if(left != -1):
            while(m - 1 >= 0 and nums[m-1] == target):
                m = m - 1  
                left = m                               
            while(m + 1 < len(nums) and nums[m+1] == target):
                m = m + 1  
                right = m 
        return [left,right]

Ideas ： Two points search , We found one , To the left and right while To find out if there are smaller and larger values .
Official interpretation ： Define a boolen It's worth it lower, Define a function , take list and target Pass in and calculate leftIndex and rightIndex.
Be careful ： Consider the boundary problem （l > 0 and r < length）.

35. Search insert location （ Simple ）

link ：https://leetcode-cn.com/problems/search-insert-position/
Title Description ： Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence . You can assume that there are no duplicate elements in the array .

solution ： Is the common binary search method . because >= when , Just move right, When middle == target when ,right Move to in the next round < lefr,left unchanged , So in the end left that will do .（ Using this method, you don't have to judge the boundary , Improper boundary judgment will result in error ）

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l , r = 0 , len(nums)-1      
        while(l<=r):
            mid=l+(r-l)//2
            if(nums[mid]<target):
                l=mid+1
            else:
                 r=mid-1       
        return l      

Be careful ：

• nums An array with the target Use... For comparison nums[m] == target
• left, right Addition and subtraction middle
• When inserting the first element , Judge right<0 instead of right<=0 ( There is no need to judge the boundary problem ）

Complexity analysis

• Time complexity ：O(logx), That is, the number of times needed for binary search .
• Spatial complexity ：O(1).

69.x The square root of （ Simple ）

link ：https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/
solution 1： Common binary search method , Because the root takes an integer , Find the ratio middle The small one will do . Because the end condition is left > right, So in the last iteration ,right That is, the value we require .
solution 2： Newton's iteration .(x+a/x)/2.（ Newton iteration method can be considered when square root is encountered ）

# Dichotomy 
class Solution:
    def mySqrt(self, x: int) -> int:
        left,right = 1,x
        while(left <= right):
            mid = left + (right - left) // 2
            if(mid * mid <= x):
                left = mid + 1
            if(mid * mid == x):
                return mid
            if(mid * mid > x):    # Don't be lazy else（ Report errors ！！！）
                right = mid - 1
        return (right)
# Newton's iteration 
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        
        C, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + C / x0)
            if abs(x0 - xi) < 1e-7:
                break
            x0 = xi
        
        return int(x0)

Complexity analysis

• Time complexity ：O(log x), This method is quadratic convergent , Faster than binary search .
• Spatial complexity ：O(1).

367. Effective complete square number （ Simple ）

link ：https://leetcode-cn.com/problems/valid-perfect-square/

solution 1： Common dichotomy . It was used 2 There are ways to achieve （ Fully closed , Left open right closed ）
solution 2： Newton's iteration

# Left closed right away 
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if(num<2):
            return True
        left = 2
        right = num // 2 + 1
        while left < right:
            x =  ( right + left) // 2
            if(x*x == num):
                return True
            elif(x*x < num):
                left = x + 1 
            else:
                right = x 
        return False
#  Iterative method 
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 2:
            return True   
        x = num // 2
        while x * x > num:
            x = (x + num // x) // 2
        return x * x == num

704. Two points search （ Simple ）

link ：https://leetcode-cn.com/problems/binary-search/
subject ： Given a n The elements are ordered （ Ascending ） integer array nums And a target value target , Write a function search nums Medium target, If the target value has a return subscript , Otherwise return to -1.

Ideas ： The simplest dichotomy .

# JS Realized 
var search = function(nums, target) {
    
    let l = 0, r = nums.length - 1;
    while(l <= r){
    
        let m = (r+l) >> 1;
        if(target === nums[m]){
    
            return m;
        }
        else if (target < nums[m]){
    
            r = m - 1;
        }
        else{
    
            l = m + 1;
        }
    }
    return -1;
};