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

34. Find the first and last positions of elements in the sorted array (medium)

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

Title Description: give an integer array nums arranged in ascending order and a target value target. Find the start and end positions of the given target value in the array. If the target value target does not exist in the array, return [- 1, - 1].

Advanced:
Can you design and implement an algorithm with time complexity of O(log n) to 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]

Idea: binary search, find one, and use while to find whether there are smaller and larger values on the left and right sides.
Official solution: define a lower with boolen value and a function to pass in list and target to calculate leftIndex and rightIndex.
Note: consider the boundary problem (L > 0 and R < length).

35. Search insertion position (simple)

Link: https://leetcode-cn.com/problems/search-insert-position/
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 the position where it will be inserted in order. You can assume that there are no duplicate elements in the array.

Solution: it is the ordinary binary search method. When > =, only right will be moved. When middle == target, right will be moved to < lefr in the next round, and left will remain unchanged, so return to left at last. (if you use this method, you don't need to judge the boundary. If the boundary is not judged properly, you will report an 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:

• When comparing nums array with target, use nums[m] == target
• left, right plus or minus 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(\log x)O(logx), which is the number of times required for binary search.
• Space complexity: O(1)O(1).

Square root of 69.x (simple)

Link: https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/
Solution 1: for the ordinary binary search method, since the root takes an integer, you can find the one smaller than the middle. Since the end condition is left > right, right is the value we require in the last iteration.
Solution 2: Newton iterative method. (x+a/x)/2. (Newton iteration method can be considered in case of square root)

#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 and use else
                right = mid - 1
        return (right)
#Newton iterative method
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 convergence and faster than binary search.
• Space complexity: O(1).

367. Effective complete square (simple)

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

Solution 1: ordinary dichotomy. It is realized by two methods (full closing, left opening and right closing)
Solution 2: Newton iterative method

#Left closed right open
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. Binary search (simple)

Link: https://leetcode-cn.com/problems/binary-search/
Title: given an n-element ordered (ascending) integer array nums and a target value target, write a function to search the target in nums. If the target value exists, return the subscript, otherwise return - 1.

Idea: the simplest dichotomy.

# JS implemented
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;
};