Leftmost Binary Search

Oct 18

If the element exists, finds its leftmost index
If it doesn’t exists, locate the index of where it should be

O(log n)

	# 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

Given arr = [1, 2, 3, 3, 3, 6, 9], this binary search implementation can:

· check whether the target exists.
arr[binarySearch(arr, 2)] == 2

· find the leftmost index of the target if it exists.
binarySearch(arr, 3) = 2
binarySearch(arr, 9) = 6

· find the index of where the target should be if it doesn't exist.
binarySearch(arr, 4) = 5
binarySearch(arr, -5) = 0
binarySearch(arr, 100) = 7

Python | Java

	def searchRange(self, nums: List[int], target: int) -> List[int]:
	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

	l = binarySearch(nums, target)
	# target does not exist. No need to look for the last position.
	if l == len(nums) or nums[l] != target:
	return [-1, -1]
	# look for the index of target + 1
	r = binarySearch(nums, target + 1)
	# last position is r - 1.
	return [l, r - 1]

	public int[] searchRange(int[] nums, int target) {
	int l = binarySearch(nums, target);
	// target does not exist. No need to look for the last position.
	if (l == nums.length \|\| nums[l] != target) return new int[] { -1, -1 };
	// look for the index of target + 1
	int r = binarySearch(nums, target + 1);
	// last position is r - 1.
	return new int[] { l, r - 1 };
	}
	private 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;
	}