Skip to main content

O(log N), O(sort)

The pure logarithmic-time family: classic search, the bisect boundary toolkit, and the dozens of variants that are really just one of those templates with a twist. When the input isn't sorted, an O(N log N) sort first still keeps us in this bucket.

The Classic Binary Search Algorithm​

The single lower-bound template that solves almost everything else on this page.

702. Search in a Sorted Array of Unknown Size​

Medium·
Solutions:
Visualize
class Solution:
def search(self, reader: "ArrayReader", target: int) -> int:
lo, hi = 0, 1
# Find the boundary indices such that the target lies in-between (low, high)
while target > reader.get(hi):
lo = hi
hi <<= 2
# Typical binary search
while lo < hi:
mid = lo + (hi - lo) // 2
if reader.get(mid) < target:
lo = mid + 1
else:
hi = mid
return lo if reader.get(lo) == target else -1

74. Search a 2D Matrix​

Medium·
Solutions:
Visualize
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
row, col = len(matrix), len(matrix[0])
get = lambda i: matrix[i // col][
i % col
] # access an element of matrix using offset 'i'
lo, hi = 0, row * col - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if get(mid) < target:
lo = mid + 1
else:
hi = mid
return get(lo) == target

Bisect Algorithms​

Four reusable insert-position primitives. Everything in the next sections calls one of these.

Bisect Left​

Easy·

Bisect Left

Solutions:
Visualize
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Left Reverse​

Easy·

Bisect Left Reverse

Solutions:
Visualize
class Solution:
def bisect_left_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] > target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] > target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Right​

Easy·

Bisect Right

Solutions:
Visualize
class Solution:
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Right Reverse​

Easy·

Bisect Right Reverse

Solutions:
Visualize
class Solution:
def bisect_right_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] > target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] >= target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Derivatives​

One bisect call, lightly post-processed.

744. Find Smallest Letter Greater Than Target​

Easy·
Solutions:
Visualize
class Solution:
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
index = self.bisect_right(letters, target)
return letters[index % len(letters)]

35. Search Insert Position​

Easy·
Solutions:
Visualize
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def searchInsert(self, nums: List[int], target: int) -> int:
return self.bisect_left(nums, target)

362. Design Hit Counter​

Medium·
Solutions:
class HitCounter:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def __init__(self):
self.hits = []
 
def hit(self, timestamp: int) -> None:
self.hits.append(timestamp)
 
def getHits(self, timestamp: int) -> int:
index = self.bisect_left(self.hits, timestamp - 300 + 1)
return len(self.hits) - index if 0 <= index < len(self.hits) else 0

Bisect Left & Right​

Call both boundaries and work with the [left, right) span between them.

34. Find First and Last Position of Element in Sorted Array​

Solutions:
Visualize
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = self.bisect_left(nums, target)
right = self.bisect_right(nums, target)
if not nums or left == right: # left==right when the element is not present
return [-1, -1]
return [left, right - 1]

2089. Find Target Indices After Sorting Array​

Solutions:
Visualize
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums = sorted(nums)
left = self.bisect_left(nums, target)
right = self.bisect_right(nums, target)
return list(range(left, right))

1150. Check If a Number Is Majority Element in a Sorted Array​

Solutions:
Visualize
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def isMajorityElement(self, nums: List[int], target: int) -> bool:
left = self.bisect_left(nums, target)
right = self.bisect_right(nums, target)
count = right - left
return count > len(nums) / 2

Element Occurrence​

Easy·
Solutions:
Visualize
def bisect_left(arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
 
def bisect_right(arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def findCount(nums: List[int], target: int):
left = bisect_left(nums, target)
right = bisect_right(nums, target)
count = right - left
return count if count != 0 else -1

Slight Variants​

The classic template with the comparison swapped for a derived predicate.

1064. Fixed Point​

Easy·
Solutions:
Visualize
class Solution:
def fixedPoint(self, arr: List[int]) -> int:
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < mid:
lo = mid + 1
else:
hi = mid
return lo if arr[lo] == lo else -1

374. Guess Number Higher or Lower​

Easy·
Solutions:
Visualize
pick = 6 # hidden target the judge knows
 
 
def guess(num):
return (num < pick) - (num > pick)
class Solution:
def guessNumber(self, n: int) -> int:
lo, hi = 0, n
while lo < hi:
mid = lo + (hi - lo) // 2
if guess(mid) == 1: # 1 if guess is lower than the target
lo = mid + 1
else: # -1 or 0 if guess is greater than or equal to the target
hi = mid
return lo

278. First Bad Version​

Easy·
Solutions:
Visualize
first_bad = 4 # hidden first bad version the judge knows
 
 
def isBadVersion(version):
return version >= first_bad
class Solution:
def firstBadVersion(self, n: int) -> int:
lo, hi = 0, n
while lo < hi:
mid = lo + (hi - lo) // 2
if isBadVersion(mid) == False:
lo = mid + 1
else:
hi = mid
return lo

441. Arranging Coins​

Easy·
Solutions:
Visualize
class Solution:
def arrangeCoins(self, n: int) -> int:
coins = lambda i: i * (i + 1) / 2
lo, hi = 0, n
while lo < hi:
mid = lo + (hi - lo) // 2
if coins(mid) <= n:
lo = mid + 1
else:
hi = mid
return lo if coins(lo) == n else lo - 1

287. Find the Duplicate Number​

Medium·
Solutions:
Visualize
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
nums = sorted(nums)
expected = lambda i: i + 1
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if expected(mid) == nums[mid]:
lo = mid + 1
else:
hi = mid
return nums[lo]

Single Element in a Sorted Array​

Medium·
Solutions:
Visualize
def singleNonDuplicate(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] == nums[mid + 1]:
mid -= 1
right_len = hi - mid
if right_len % 2 == 1:
lo = mid + 1
else:
hi = mid
return nums[lo]

Math - Square​

Binary search over a numeric answer range to invert a monotone math function.

69. Sqrt(x)​

Easy·
Solutions:
Visualize
class Solution:
def mySqrt(self, x: int) -> int:
square = lambda i: i * i
lo, hi = 0, x
while lo < hi:
mid = lo + (hi - lo) // 2
if square(mid) <= x:
lo = mid + 1
else:
hi = mid
return lo if square(lo) == x else lo - 1

367. Valid Perfect Square​

Solutions:
Visualize
class Solution:
def isPerfectSquare(self, num: int) -> bool:
square = lambda i: i * i
lo, hi = 0, num
while lo < hi:
mid = lo + (hi - lo) // 2
if square(mid) <= num:
lo = mid + 1
else:
hi = mid
lo = lo if square(lo) == num else lo - 1
return square(lo) == num

633. Sum of Square Numbers​

Medium·
Solutions:
Visualize
class Solution:
def isPerfectSquare(self, num: int) -> bool:
square = lambda i: i * i
lo, hi = 0, num
while lo < hi:
mid = lo + (hi - lo) // 2
if square(mid) <= num:
lo = mid + 1
else:
hi = mid
lo = lo if square(lo) == num else lo - 1
return square(lo) == num
def judgeSquareSum(self, c: int) -> bool:
for a in range(0, int(c**0.5) + 1):
b = c - a * a
if self.isPerfectSquare(b):
return True
return False

Missing Elements​

Bisect on a "how many are missing so far" predicate.

268. Missing Number​

Solutions:
Visualize
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if mid >= nums[mid]:
lo = mid + 1
else:
hi = mid
return lo

1060. Missing Element in Sorted Array​

Solutions:
Visualize
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
missing = (
lambda i: nums[i] - nums[0] - i
) # Return the number of missing numbers
lo, hi = 0, len(nums)
# find first greatest `missing` that is <= k
while lo < hi:
mid = lo + (hi - lo) // 2
if missing(mid) < k:
lo = mid + 1
else:
hi = mid
return nums[lo - 1] + (k - missing(lo - 1))

1539. Kth Missing Positive Number​

Solutions:
Visualize
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
missing = lambda i: arr[i] - 1 - i # Return the number of missing numbers
lo, hi = 0, len(arr)
# find first greatest `missing` that is <= k
while lo < hi:
mid = lo + (hi - lo) // 2
if missing(mid) < k:
lo = mid + 1
else:
hi = mid
return arr[lo - 1] + (k - missing(lo - 1))

Rotated Sorted Array​

Locate the pivot (minimum), then search the right half.

Find the Pivot (Minimum)​

Find the Pivot (Minimum)

Solutions:
Visualize
class Solution:
def findPivot(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[hi] < nums[mid]:
lo = mid + 1
elif nums[hi] > nums[mid]:
hi = mid
else:
hi -= 1
return lo

154. Find Minimum in Rotated Sorted Array II​

Solutions:
Visualize
class Solution:
def findPivot(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[hi] < nums[mid]:
lo = mid + 1
elif nums[hi] > nums[mid]:
hi = mid
else:
hi -= 1
return lo
def findMin(self, nums: List[int]) -> int:
pivot = self.findPivot(nums)
return nums[pivot]

153. Find Minimum in Rotated Sorted Array​

Solutions:
Visualize
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]

33. Search in Rotated Sorted Array​

Solutions:
Visualize
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def findPivot(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[hi] < nums[mid]:
lo = mid + 1
elif nums[hi] > nums[mid]:
hi = mid
else:
hi -= 1
return lo
def search(self, nums: List[int], target: int) -> int:
pivot = self.findPivot(nums)
left = self.bisect_left(nums, target, lo=0, hi=pivot)
if left < len(nums) and nums[left] == target:
return left
right = self.bisect_left(nums, target, lo=pivot, hi=len(nums))
if right < len(nums) and nums[right] == target:
return right
return -1

Peaks in an Array​

Walk uphill: compare the midpoint to its neighbor and move toward the larger side.

162. Find Peak Element​

Solutions:
Visualize
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo

852. Peak Index in a Mountain Array​

Solutions:
Visualize
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo

1095. Find in Mountain Array​

Solutions:
Visualize
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_left_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] > target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] > target:
lo = mid + 1
else:
hi = mid
return lo
 
def peakIndexInMountainArray(self, arr: List[int]) -> int:
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo
def findInMountainArray(self, target: int, mountain_arr: "MountainArray") -> int:
mountain_arr = CustomMountainArray(mountain_arr)
peakIndex = self.peakIndexInMountainArray(mountain_arr)
left = self.bisect_left(mountain_arr, target, lo=0, hi=peakIndex)
if mountain_arr[left] == target:
return left
right = self.bisect_left_rev(
mountain_arr, target, lo=peakIndex, hi=len(mountain_arr) - 1
)
if right < len(mountain_arr) and mountain_arr[right] == target:
return right
return -1
 
 
class CustomMountainArray:
def __init__(self, ma):
self.mountain_arr = ma
 
def __len__(self):
return self.mountain_arr.length()
 
def __getitem__(self, key):
return self.mountain_arr.get(key)

H-Index​

Find the crossover point where citations meet the rank-from-the-end count.

275. H-Index II​

Medium·
Solutions:
Visualize
class Solution:
def hIndex(self, citations: List[int]) -> int:
cited = lambda i: len(citations) - i
lo, hi = 0, len(citations) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if cited(mid) > citations[mid]:
lo = mid + 1
else:
hi = mid
return cited(lo) if citations[lo] >= cited(lo) else 0

274. H-Index​

Medium·
Solutions:
Visualize
class Solution:
def hIndex(self, citations: List[int]) -> int:
citations = sorted(citations)
cited = lambda i: len(citations) - i
lo, hi = 0, len(citations) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if cited(mid) > citations[mid]:
lo = mid + 1
else:
hi = mid
return cited(lo) if citations[lo] >= cited(lo) else 0