Practice #015: Leetcode - Binary Search
Binary Search: Template 1
- Condition: Needed only the pivot to decide the direction of the search.
- Termination: \(s > e\) and there is no more candidates to process.
Leetcode: 704. Binary Search
from typing import List class Solution: def search(self, nums: List[int], target: int) -> int: n = len(nums) s = 0 e = n - 1 while s <= e: m = s + (e - s) // 2 if nums[m] == target: return m elif nums[m] > target: e = m - 1 else: s = m + 1 return -1 assert Solution().search([-1, 0, 3, 5, 9, 12], 9) == 4 assert Solution().search([-1, 0, 3, 5, 9, 12], 2) == -1
Leetcode: 69. Sqrt(x)
class Solution: def mySqrt(self, x: int) -> int: s = 0 e = x while s <= e: m = s + (e - s) // 2 p = m * m if p == x: return m elif p > x: e = m - 1 else: s = m + 1 return e assert Solution().mySqrt(4) == 2 assert Solution().mySqrt(8) == 2
Leetcode: 374. Guess Number Higher or Lower
# The guess API is already defined for you. # @param num, your guess # @return -1 if num is higher than the picked number # 1 if num is lower than the picked number # otherwise return 0 # def guess(num: int) -> int: class Solution: def guessNumber(self, n: int) -> int: s = 1 e = n while s <= e: m = s + (e - s) // 2 v = guess(m) if v == 0: return m elif v == -1: e = m - 1 elif v == +1: s = m + 1
Binary Search: Template 2
- Condition: Needed pivot and next element to decide the direction of the search.
- Termination: \(s = e\) and there is one candidate to process.
Leetcode: 278. First Bad Version
Can we formulate the problem as searching the last element that satisfy a condition? If \(isBadVersion(m)=true\), we know that either \(m\) is the answer for the problem or a number smaller than it. So, we are looking for the first bad version which is equivalent to the last good version plus one.
# The isBadVersion API is already defined for you. # @param version, an integer # @return an integer # def isBadVersion(version): class Solution: def firstBadVersion(self, n): s = 1 e = n while s < e: m = s + (e - s) // 2 if isBadVersion(m): e = m else: s = m + 1 return s
Leetcode: 162. Find Peak Element
Can we formulate the problem as searching the last element that satisfy a condition? Be \(m\) an index of the array. If \(nums[m]from typing import List
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
n = len(nums)
inf = 2**63
s = 0
e = n - 1
while s < e:
m = s + (e - s) // 2
if nums[m] < nums[m + 1]:
s = m + 1
else:
e = m
return s
assert Solution().findPeakElement([1, 2, 3, 1]) == 2
assert Solution().findPeakElement([1, 2, 1, 3, 5, 6, 4]) == 5
Binary Search: Template 3
- Condition: Needed pivot and prev element to decide the direction of the search.
- Termination: \(s + 1 = e\) and there are two candidates to process.
Leetcode: 34. Find First and Last Position of Element in Sorted Array
Can we state the problem as result of multiple searches? Find the first occurrence of \(target\) in the array and the first occurrence of \(target+1\) and derive the range from them.
from typing import List class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: n = len(nums) if n == 0: return [-1, -1] def search(target): s = 0 e = n - 1 while s < e: m = s + (e - s) // 2 if nums[m] < target: s = m + 1 else: e = m return s l = search(target) if nums[l] != target: return [-1, -1] r = search(target + 1) return [l, r - 1 if nums[r] != target else r] assert Solution().searchRange([5, 7, 7, 8, 8, 10], 8) == [3, 4] assert Solution().searchRange([5, 7, 7, 8, 8, 10], 6) == [-1, -1] assert Solution().searchRange([], 0) == [-1, -1]
Leetcode: 658. Find K Closest Elements
Can we reuse or extend a solution from a sub-problem to solve the next sub-problem more efficiently? Suppose that we know the index \(k\) of closest element of \(x\). Then, we can start with the interval \(arr[i..i]\) and extend to the side that has the next closest element. This process will end when the \(k\) closest elements were found solving the problem. To find such \(i\), we can use a binary-search, since \(arr[i] - x < 0\) means that we are to the left of the desired position and therefore we can keep searching to right of \(i\), otherwise we search on the left subarray of \(i\). Time complexity and space is \(O(k)\).
from typing import List class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: n = len(arr) s = 0 e = n - 1 def value(m): if m < 0 or m == n: return 2**64 return abs(arr[m] - x) def best(a, b): return value(a) < value(b) or (value(a) == value(b) and arr[a] < arr[b]) while s < e: m = s + (e - s) // 2 if arr[m] - x < 0: s = m + 1 else: e = m if best(s - 1, s): s = e = s - 1 while e - s + 1 < k: if best(s - 1, e + 1): s = s - 1 else: e = e + 1 return arr[s : e + 1] assert Solution().findClosestElements([1, 2, 3, 4, 5], 4, 3) == [1, 2, 3, 4] assert Solution().findClosestElements([1, 2, 3, 4, 5], 4, -1) == [1, 2, 3, 4]