Binary Search
Notes
# For finding an exact value (Is mid the answer?) def binarySearch1(nums, target): left, right = 0, len(nums) - 1 # Use <= because mid is always discarded while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid if nums[mid] > target: right = mid - 1 else: left = mid + 1 return -1 # For shrinking boundaries (Is mid a valid first answer?) def binarySearch2(nums, target): left, right = 0, len(nums) - 1 # Use < because mid may be kept while left < right: mid = (left + right) // 2 if nums[mid] >= target: right = mid else: left = mid + 1 if nums[left] == target: return left return -1
Time: O(log n)
Space: O(1)
Search Insert Position (Easy)
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
Write an algorithm with O(log n) runtime complexity.
def searchInsert(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid if nums[mid] > target: right = mid - 1 else: left = mid + 1 return left
Time: O(log n)
Space: O(1)
Search a 2D Matrix (Medium)
You are given an m x n integer matrix matrix with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
Write a solution in O(log(m * n)) time complexity.
def searchMatrix(matrix: List[List[int]], target: int) -> bool: # Two binary searches to find row in matrix and target in row start, end = 0, len(matrix) - 1 while start <= end: mid = (start + end) // 2 if matrix[mid][0] <= target <= matrix[mid][-1]: break if target < matrix[mid][0]: end = mid - 1 else: start = mid + 1 if start > end: return False start, end, row = 0, len(matrix[0]) - 1, matrix[mid] while start <= end: mid = (start + end) // 2 if row[mid] == target: return True if row[mid] > target: end = mid - 1 else: start = mid + 1 return False
Time: O(log (m * n))
Space: O(1)
Find Peak Element (Medium)
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
Assume nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
Assume nums[i] != nums[i + 1] for all valid i.
Write an algorithm that runs in O(log n) time.
def findPeakElement(nums: List[int]) -> int: # Check boundaries now and ignore later if len(nums) == 1 or nums[0] > nums[1]: return 0 if nums[-1] > nums[-2]: return len(nums) - 1 left, right = 1, len(nums) - 2 while left <= right: mid = (left + right) // 2 prev, curr, nxt = nums[mid - 1], nums[mid], nums[mid + 1] if prev < curr > nxt: return mid # Peak is guaranteed to exist on side with larger num, given assumptions elif prev > curr: right = mid - 1 else: left = mid + 1
Time: O(log n)
Space: O(1)
Search in Rotated Sorted Array (Medium)
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
Write an algorithm with O(log n) runtime complexity.
def search(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # One side must be sorted # Left side is sorted if nums[left] <= nums[mid]: # Left side contains target if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # Right side is sorted else: # Right side contains target if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1
Time: O(log n)
Space: O(1)
Find First and Last Position of Element in Sorted Array (Medium)
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Write an algorithm with O(log n) runtime complexity.
def searchRange(nums: List[int], target: int) -> List[int]: answer = [-1, -1] # Find first index left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: answer[0] = mid if nums[mid] >= target: right = mid - 1 else: left = mid + 1 # Find last index left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: answer[1] = mid if nums[mid] <= target: left = mid + 1 else: right = mid - 1 return answer
Time: O(log n)
Space: O(1)
Find Minimum in Rotated Sorted Array (Medium)
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2]if it was rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
Write an algorithm that runs in O(log n) time.
def findMin(nums: List[int]) -> int: left, right = 0, len(nums) - 1 # Exit loop when left == right while left < right: mid = (left + right) // 2 # The rotated start is on the right side if nums[mid] > nums[right]: # Skip mid since it cannot be the answer left = mid + 1 else: right = mid return nums[left]
Time: O(log n)
Space: O(1)
Alternative answer:
def findMin(nums: List[int]) -> int: left, right = 0, len(nums) - 1 # Exit loop when left == right while left < right: # Early check: range is sorted if nums[left] < nums[right]: return nums[left] mid = (left + right) // 2 # The rotated start is on the left side -> go left if nums[left] > nums[mid]: # Cannot skip mid, which could be answer right = mid # The left side is sorted -> go right # This is bad if the entire range is sorted else: left = mid + 1 return nums[left]
Time: O(log n)
Space: O(1)