Data structures and algorithms · Lesson 23 of 60 · Code lesson, JavaScript or Python · Optional
Searching algorithms
Searching means finding where a value is, or finding out that it is missing.
Linear search checks items one by one, so it can take as many steps as there are items.
Binary search works on sorted data and halves the search area each step, so it needs only a handful of steps.
Worked example
In JavaScript, Math.floor((low + high) / 2) finds the middle index, and low and high mark the part still being searched.
const numbers = [4, 8, 15, 16];
console.log(numbers.indexOf(15));Output: 2
In Python, (low + high) // 2 finds the middle index, and low and high mark the part still being searched.
numbers = [4, 8, 15, 16]
print(numbers.index(15))Output: 2
Your turn
Finish the binary search. The program reads sorted numbers and a target, and prints the target's index or -1. In each branch, throw away the half that cannot hold the target.
Your program is checked with these 3 inputs:
Input:
1 3 5 7 9 7
Expected output:
3
Input:
1 3 5 7 9 4
Expected output:
-1
Input:
2 4 6 4
Expected output:
1
Loading your practice…
Preparing your workspace…