Leftmost Binary Search

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

O(log n)

Python | Java

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

LeetCode

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

Python | Java

• Relevant Problems

  https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

  https://leetcode.com/problems/search-insert-position/

  https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/

  https://leetcode.com/problems/first-bad-version/

  https://leetcode.com/problems/find-smallest-letter-greater-than-target/

  https://leetcode.com/problems/sqrtx/

  https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

  https://leetcode.com/problems/random-pick-with-weight/

  https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

  https://leetcode.com/problems/koko-eating-bananas/

  https://leetcode.com/problems/split-array-largest-sum/

  https://leetcode.com/problems/divide-chocolate/

  https://leetcode.com/problems/missing-element-in-sorted-array/