Binary Search

O(log n)
n = size(array)

Python | Java

	# If the target exists, returns its leftmost index.
	# Else, returns the index of where it should be.
	def binarySearch(nums: List[int], target: int) -> int:
	l, r = 0, len(nums)
	while l < r :
	m = (l + r) // 2;
	if nums[m] < target:
	l = m + 1;
	else:
	r = m;
	return l;

view raw binarySearch.py hosted with ❤ by GitHub

	// If the target exists, returns its leftmost index.
	// Else, returns the index of where it should be.
	int binarySearch(int[] nums, int target) {
	int l = 0, r = nums.length;
	while (l < r) {
	int m = (l + r) / 2;
	if (nums[m] < target) l = m + 1;
	else r = m;
	}
	return l;
	}

view raw BinarySearch.java hosted with ❤ by GitHub

Tricks

Leftmost Binary Search