Find the first index where a predicate becomes true (or last where it's false)
When to useFirst/last occurrence, leftmost/rightmost insertion point, transition point
iterative
Find the First True in a Sorted Boolean Array
binary_search_boundaryFirst Element Not Smaller Than Target
binary_search_first_element_not_smaller_than_targetFind Minimum in Rotated Sorted Array
min_in_rotated_sorted_arrayThe Peak of a Mountain Array
peak_of_mountain_arrayCompare Strings
google_oa_compare_stringsRussian Doll Envelopes
russian_doll_envelopesFind First And Last Positionmedium
find_first_and_last_position · no slotsINITIALIZE
lo = 0, hi = arr.length (note: not arr.length - 1)
let lo = 0, hi = arr.length;
let lo = 0, hi = arr.length;
let lo = 0, hi = arr.length;
let lo = 0, hi = arr.length - 1;
let lo = 0, hi = counts1.length;
envelopes.sort((a,b) => a[0]!==b[0] ? a[0]-b[0] : b[1]-a[1]);const tails = [];
—
TRAVERSE
while (lo < hi)
while (lo < hi) {
while (lo < hi) {
while (lo < hi) {
while (lo < hi) {
while (lo < hi) {
for (const [, h] of envelopes) {
—
mid
mid = Math.floor((lo + hi) / 2)
const mid = Math.floor((lo + hi) / 2);
const mid = Math.floor((lo + hi) / 2);
const mid = Math.floor((lo + hi) / 2);
const mid = Math.floor((lo + hi) / 2);
const mid = Math.floor((lo + hi) / 2);
—
—
[PREDICATE]
if predicate(mid) hi = mid; else lo = mid + 1
if (arr[mid]) hi = mid;else lo = mid + 1;
if (arr[mid] >= target) hi = mid;else lo = mid + 1;
if (arr[mid] <= arr[arr.length - 1]) hi = mid;else lo = mid + 1;
if (arr[mid] > arr[mid + 1]) hi = mid;else lo = mid + 1;
if (counts1[mid] < target) lo = mid + 1;else hi = mid;
if (tails[mid] < h) lo = mid + 1;else hi = mid;}
—
RETURN
return lo (the boundary)
return lo === arr.length ? -1 : lo;
return lo;
return lo;
return lo;
return lo;
return tails.length;
—