LC34, LC35, LC69, & LC367 (with template)

Solutions to LeetCode 34 Find First and Last Position of Element in Sorted Array, LeetCode 35 Search Insert Position, LeetCode 69 Sqrt(x), & LeetCode 367 Valid Perfect Square, and a template for binary search.

LeetCode 34

Find First and Last Position of Element in Sorted Array (Medium) [link]

Use binary search because the problem is asking for O(log n) time complexity.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        lower = self.lowerBound(nums, target)
        upper = self.upperBound(nums, target)

        if lower == upper:
            return [-1,-1]
        
        return [lower, upper-1]

    def lowerBound(self, nums, target):
        l = 0
        r = len(nums)
        while l < r:
            m = l + (r - l)//2
            if nums[m] >= target:
                r = m
            else:
                l = m+1
        return l

    def upperBound(self, nums, target):
        l = 0
        r = len(nums)
        while l < r:
            m = l + (r - l)//2
            if nums[m] > target:
                r = m
            else:
                l = m+1
        return l

LeetCode 35

Search Insert Position (Easy) [link]

The required position satisfies nums[pos-1]<target<=nums[pos]. The idea is to binary search to find the index of the first number that is larger or equal to the target.

Notice that eventually r=l. To find the index of the max number that satisfies target <= nums[pos], we rely on the first if clause.

Time complexity O(log n), space complexity O(1).

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

LeetCode 69

Sqrt(x) (Easy) [link]

We want to find the smallest m such that m*m > x, or the largest m such that m*m <= x. We need to minus 1 from m because the square of the integer part could be smaller.

Time complexity is O(logx). Space complexity O(1).

class Solution:
    def mySqrt(self, x: int) -> int:
        l = 0
        r = x+1 # [l,r)
        while l<r:
            m = l + (r-l)//2
            if m*m > x: # finding upper bound
                r = m
            else:
                l = m+1
        return l-1

class Solution:
    def mySqrt(self, x: int) -> int:
        l = 0
        r = x+1
        while l<r:
            m = l + (r-l)//2
            if m*m <= x: # finding upper bound
                l = m+1
            else:
                r = m
        return l-1

LeetCode 367

Valid Perfect Square (Easy) [link]

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l = 0
        r = num+1
        while l < r:
            m = l + (r-l)//2
            if m*m == num:
                return True
            if m*m >= num:
                r = m
            else:
                l = m+1
        return False

Template for Binary Search

Sometime we need f(m) to determine whether m is the solution. g(m) is used to determine the side of the solution. Usually g(m) is given in the problem. We can consider binary_search works to “find the smallest l such that g(m) is true”.

Time complexity of binary_search is O(log(r-l) * (f(m) + g(m))), space complexity is O(1). Note that the time and space complexity of g(m) depends on the problem, and the space complexity O(1) does not include the space complexity of g(m).

def binary_search(l, r): # [l,r)
    while l < r:
        m = l + (r - l) // 2
        if f(m):
            return m 
        if g(m):
              r = m # new range [l, m)
        else:
            l = m + 1 # new range [m+1, r)
    return l

Application of this Template

1] Find the index of a specified element in a sorted unique array.

def binary_tree(array, val):
    l = 0
    r = len(array)
    while l < r:
        m = l + (r - l) // 2
        if array[m] == val:
            return m
        if array[m] > val:
            l = m
        else:
            r = m + 1
    return -1 # not found

2] Find the lower bound and upper bound of a val in a sorted array.

lower_bound works to find the first index such that A[index] > = val. upper_bound works to find the first index such that A[index] > val.

def lower_bound(array, val):
    l = 0
    r = len(array)
    while l < r:
        m = l + (r - l) // 2
        if A[m] >= val:
            r = m
        else:
            l = m + 1
    return l

def upper_bound(array, val):
    l = 0
    r = len(array)
    while l < r:
        m = l + (r - l) // 2
        if A[m] > val:
            r = m
        else:
            l = m + 1
    return l

Two Ways of Defining Range

Binary Search: given a function g, returns the smallest m in the given range such that g(m) is True. Find a split point m such that for all n (n >= m), conditions are satisfied, then m will become the answer.

• [l, r)

  In this case, strictly speaking, r should be n + 1, and can overflow if n = 2^31 -1. Sometimes, it’s doable to let r = n, after binary searching if the answer cannot be foun d from 1 to n-1, then n must be the answer so we return n.

  def binary_search(l, r):
      while l < r:
          m = l + (r - l) // 2
          if g(m):
              r = m # range [l, m)
          else:
              l = m + 1 # range [m + 1, r)
      return l
  

• [l, r]

  def binary_search(l, r):
        while l <= r:
          m = l + (r - l) // 2
          if g(m):
              r = m - 1 # range [l, m - 1]
          else:
              l = m + 1 # range [m + 1, r]
      return l