DAY 87 OF 90 · The loops under DSA

First not smaller

Medium90 Days of Looping

Inputs

values is a list of 0 to 14 whole numbers in increasing order, each from 0 to 40. x is a whole number from 0 to 45.

Your tasks

Set low to 0 and high to len(values).
Use a while loop that runs while low < high. Look at mid, halfway between them (rounded down). If values[mid] < x, move low to mid + 1. Otherwise move high to mid.
Complete lowerBound so it returns low, the position of the first number that is at least x. Return it, do not print it.

Example

With values = [1, 3, 3, 3, 8, 12] and x = 3, lowerBound returns 1.

Rules

If every number is smaller than x, return len(values).
Numbers may repeat. Return the earliest position.

Test data

TEST DATA 1: values is [1, 3, 3, 3, 8, 12], x is 3

TEST DATA 2: values is [2, 4], x is 9

Practice focus

Prefix sums, counting, binary search, best stretch and sorting, all written as plain loops. This is where loops turn into named algorithms. You have already written the loops.

Day 86 Day 88 All 90 days