DAY 86 OF 90 · The loops under DSA

Binary search

Medium90 Days of Looping

Inputs

values is a list of 0 to 14 different whole numbers in increasing order, each from 0 to 60. target is a whole number from 0 to 60.

Your tasks

Set low to 0 and high to the last position.
Use a while loop that runs while low <= high. Look at the middle position mid (halfway between low and high, rounded down).
If values[mid] is the target, return mid. If it is too small, move low to mid + 1. If it is too big, move high to mid - 1.
Complete binarySearch so it returns the position of target, or -1. Return it, do not print it.

Example

With values = [2, 5, 9, 14, 21, 30] and target = 14, binarySearch returns 3.

Rules

Do not look at every number. Halve the search each time.

Test data

TEST DATA 1: values is [2, 5, 9, 14, 21, 30], target is 14

TEST DATA 2: values is [1, 3], target is 2

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 85 Day 87 All 90 days