Skills for tackling LeetCode problems - Modified Binary Search.
Binary search can be used to find a certain element in a given sorted Array or LinkedList or Matrix.
1. Order-Agnostic Binary Search
Given a sorted array of numbers, find if a given number ‘key’ is present in the array. Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order. And we should assume the array has duplicates. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.
# Time complexity O(log N). Space complexity O(1).
def binary_search(arr,key):
l, r = 0, len(arr) - 1
ascending = arr[l] < arr[r]
while l < r: # [l, r)
m = l + (r - l) // 2
if key == arr[m]:
return m
if ascending:
if key < arr[m]:
r = m
else:
l = m + 1
else:
if key > arr[m]:
r = m
else:
l = m + 1
return l if arr[l] == key else -1
def binary_search(arr,key):
l, r = 0, len(arr) - 1
ascending = arr[l] < arr[r]
while l <= r: # [l, r]
m = l + (r - l) // 2
if key == arr[m]:
return m
if ascending:
if key < arr[m]:
r = m - 1
else:
l = m + 1
else:
if key > arr[m]:
r = m - 1
else:
l = m + 1
return -1
2. Ceiling of a Number
Given an array of numbers sorted in an ascending order, find the ceiling of a given number ‘key’. The ceiling of ‘key’ will be the smallest element in the given array greater than or equal to the ‘key’.
# Time complexity O(log N). Space complexity O(1).
def search_ceiling_of_a_number(arr,key):
if key > arr[len(arr) -1]:
return -1
l, r = 0, len(arr) -1
while l < r:
m = l + (r - l) // 2
if key < arr[m]:
r = m
elif key > arr[m]:
l = m + 1
else:
return m
return l
Similar problems: Given an array of numbers sorted in ascending order, find the floor of a given number ‘key’. The floor of the ‘key’ will be the biggest element in the given array smaller than or equal to the ‘key’. Write a function to return the index of the floor of the ‘key’. If there is not a floor, return -1.
def search_floor_of_a_number(arr, key):
if key < arr[0]:
return -1
l, r = 0, len(arr) -1
while l < r:
m = l + (r - l) // 2
if key > arr[m]:
l = m + 1
elif key < arr[m]:
r = m
else:
return m
return r if arr[l] <= key else r-1
3. Next Letter
Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’. Assume the given array is a circular list, which means that the smallest letter in the given array is greater than the last letter of the array and is also the first letter of the array. Write a function to return the next letter of the given ‘key’.
# Time complexity O(Log N). Space complexity O(1).
def search_next_letter(letters, key):
l, r = 0, len(letters) - 1
while l < r:
m = l + (r - l) // 2
if key < letters[m]:
r = m
else:
l = m + 1
return letters[l % len(letters)] if letters[l % len(letters)] > key else letters[0]
4. Number Range
Given an array of numbers sorted in ascending order, find the range of a given number ‘key’. The range of the ‘key’ will be the first and last position of the ‘key’ in the array. Write a function to return the range of the ‘key’. If the ‘key’ is not present return [-1, -1].
# Time complexity O(log N). Space complexity O(1).
def find_range(arr, key):
result = [-1, -1]
result[0] = binary_search(arr, key, False)
if result[0] != -1:
result[1] = binary_search(arr, key, True)
return result
def binary_search(arr, key, flag):
Index = -1
l, r = 0, len(arr) - 1
while l < r:
m = l + (r - l) // 2
if key < arr[m]:
r = m
elif key > arr[m]:
l = m + 1
else:
Index = m
if flag: # search ahead to find the second index of key.
l = m + 1
else: # search behind to find the first index of key.
r = m
return Index
5. Search in a Sorted Infinite Array
Given an infinite sorted array(or an array with unknown size), find if a given number ‘key’ is present in the array. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.
# first find the bound of the array and then perform a binary search
# Time complexity O(log N). Space complexity O(1).
import math
class ArrayReader:
def __init__(self, arr):
self.arr = arr
def get(self, index):
if index >= len(self.arr):
return math.inf
return self.arr[index]
def search_in_infinite_array(reader, key):
start, end = 0, 1
while reader.get(end) < key:
newStart = end + 1 # since the index of key is larger than end, we search the range above the end
end += (end - start + 1) * 2 # double the bound each time
start = newStart
return binary_search(reader, key, start, end)
def binary_search(reader, key, l, r):
while l < r:
m = l + (r - l) // 2
if key < reader.get(m):
r = m
elif key > reader.get(m):
l = m + 1
else:
return m
return -1
6. Minimum Difference Element
Given an array of numbers sorted in ascending order, find the element in the array that has the minimum difference with the given ‘key’.
# Time complexity O(Log N). Space complexity O(1).
def search_min_diff_element(arr, key):
if key < arr[0]:
return arr[0]
if key > arr[len(arr) - 1]:
return arr[len(arr)-1]
l, r = 0, len(arr) -1
while l < r:
m = l + (r - l) // 2
if key < arr[m]:
r = m
elif key > arr[m]:
l = m + 1
else:
return arr[m]
if (arr[r] - key) < (key - arr[l-1]):
return arr[r]
return arr[l-1]
7. Bitonic Array Maximum
Find the maximum value in a given Bitonic array. An array is considered bionic if it is monotonically increasing and then monotonically decreasing.
# Time complexity O(log N). Space complexity O(1).
def find_max_in_bitonic_array(arr):
l, r = 0, len(arr) - 1
while l < r:
m = l + (r - l) // 2
if arr[m] > arr[m + 1]:
r = m
else:
l = m + 1
return arr[l]
