A Python template to solve problems involving binary search.

DSA_BinarySearchTemplate.py

"""
A Python template to solve problems involving binary search.
Template based on this post: https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/discuss/769704/Python-Clear-explanation-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems.
"""
def binary_search(array) -> int:
	def condition(value) -> bool:
		# Conditional logic based on question
		# Returns true if current value satisfies requirements
		# binary search will take care of finding the minimal val
		return
	
	left, right = 0, len(array)-1  # Include all possible elements
	while left < right:
		mid = left + (right-left) // 2  # To prevent overflow
		if condition(mid):
			right = mid
		else:
			left = mid + 1
	return left  # left is the minimal val satisfying condition, sometimes may left-1 is required

"""
Example usage of template
Problem: https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/
Solution: https://github.com/siddydutta/Daily-LeetCoding-Challenges/blob/master/2021-11-November-LeetCoding-Challenge/Kth%20Smallest%20Number%20in%20Multiplication%20Table.py
"""