Binary Search Advanced

Catalogue

1. 1. Advanced Topic
   1. 1.1. 162. Find Peak Element
   2. 1.2. 4. Median of Two Sorted Arrays
   3. 1.3. 29. Divide Two Integers
   4. 1.4. 658. Find K Closest Elements
   5. 1.5. 300. Longest Increasing Subsequence
   6. 1.6. 275. H-Index II
   7. 1.7. 774. Minimize Max Distance to Gas Station

Advanced Topic

---

162. Find Peak Element

class Solution(object):
    def findPeakElement(self, nums):
        nums = [-float('inf')] + nums + [-float('inf')]
        start, end = 1, len(nums) - 2
        while start <= end:
            mid = start + (end - start) / 2
            if nums[mid] <= nums[mid-1]:
                end = mid - 1
            elif nums[mid] <= nums[mid+1]:
                start = mid + 1
            else:
                return mid-1
        return -1

4. Median of Two Sorted Arrays

• Input Two Sorted Array. How to do Binary Search?
• Stick with the edge case, like len(nums) <= 1 and len is odd or even!!!

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)

        start, end = 0, m
        k = (m + n) // 2
        while start <= end:
            cut1 = start + (end - start) // 2
            cut2 = k - cut1
            # Deal with edge case 1 : length
            l1 = nums1[cut1-1] if cut1 > 0 else -float('inf')
            l2 = nums2[cut2-1] if cut2 > 0 else -float('inf')
            r1 = nums1[cut1] if cut1 < m else float('inf')
            r2 = nums2[cut2] if cut2 < n else float('inf')
            if l1 > r2:
                end = cut1 - 1
            elif l2 > r1:
                start = cut1 + 1
            else:
                # Deal with the edge case 2 : odd or even!
                if (m+n) % 2:
                    return min(r1, r2)
                else:
                    return (max(l1,l2) + min(r1,r2)) / 2.0

29. Divide Two Integers

Division simply requires us to find how many times we can subtract the divisor from the the dividend without making the dividend negative

• i 1, 2, 4, 8, 16, 32, 64 …
• i 1, 2, 4, 8, …
• i …
• i 1

# Same Thought
class Solution(object):
    def divide(self, dividend, divisor):
        np = (dividend < 0) ^ (divisor < 0)
        dividend = abs(dividend)
        divisor = abs(divisor)
        res = 0
        while dividend >= divisor:
            tmp, i = divisor, 1
            while dividend >= tmp:
                dividend -= tmp
                res += i
                i = i << 1
                tmp = tmp << 1
        if np:
            res = -res
        return min(max(-2147483648, res), 2147483647)

• clean

class Solution(object):
    def divide(self, dividend, divisor):
        sign = (dividend > 0) ^ (divisor > 0)
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        i = 1
        div = divisor
        while dividend >= div:
            dividend -= div
            res += i
            i = i << 1
            div = div << 1
            if dividend < div: # when div bigger enough that dividend can not minus it
                i = 1
                div = divisor

        if sign: res = -res
        return min(max(-2147483648, res), 2147483647)

658. Find K Closest Elements

• two pointers + binary search

class Solution(object):
    def findClosestElements(self, arr, k, x):
        if x <= arr[0]:
            return arr[:k]
        elif x >= arr[-1]:
            return arr[-k:]
        else:
            index = bisect.bisect_left(arr, x)
            left = max(0, index-k)
            right = min(len(arr)-1, index+k-1)
            while right - left > k-1:
                if arr[right] - x >= x - arr[left]:
                    right -= 1
                else:
                    left += 1
            return arr[left:right+1]

300. Longest Increasing Subsequence

• Use DP, we can have the O(n^2). It is hard to give the O(nlogn) solution

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums: return 0

        n = len(nums)
        ends = [nums[0]]
        for i in xrange(1, n):
            if nums[i] > ends[-1]:
                ends.append(nums[i])
                continue

            start, end = 0, len(ends)-1
            while start < end:
                mid = start + (end - start) / 2
                if ends[mid] < nums[i]:
                    start = mid + 1
                else:
                    end = mid
            ends[start] = nums[i]
        return len(ends)

275. H-Index II

class Solution(object):
    def hIndex(self, citations):
        if not citations:
            return 0

        n = len(citations)
        if citations[-1] < 1:
            return 0

        start, end = 0, n-1
        while start < end:
            mid = start + (end - start) // 2
            if citations[mid] >= n - mid:
                end = mid
            else:
                start = mid + 1
        return n-start

774. Minimize Max Distance to Gas Station

• use valid function => Binary Search the results!!!

  class Solution(object):
      def minmaxGasDist(self, stations, K):
          def valid(D):
              return sum([int((p2-p1) / D) for p1, p2 in zip(stations, stations[1:])]) <= K
  
          start, end = 0, stations[-1]-stations[0]
          while end - start > 1e-6:
              mid = (start + end) / 2.0
              if valid(mid):
                  end = mid
              else:
                  start = mid
          return start