Simple search vs Binary search

by Aditya Y. Bhargava

This book is aimed at anyone who knows the basics of coding and wants to understand algorithms. Maybe you already have a coding problem and are trying to find an algorithmic solution.

1. Introduction to #algorithms

In this chapter:

• You get a foundation for the rest of the book.
• You write your first search algorithm (binary search)
• You learn how to talk about the running time of an algorithm (Big O notation).
• You’re introduced to a common technique for designing algorithms (recursion).

Binary search

Binary search is an #algorithm; its input is a sorted list of elements. If an element you’re looking for is in that list, binary search returns the position where it’s located.

Otherwise, binary search returns null.

Simple search vs Binary search

Simple search (maybe stupid search would be a better term). With each guess, you’re eliminating only one number. If my number was 99, it could take you 99 guesses to get there!

With binary search, you guess the middle number and eliminate half the remaining numbers every time. Let me explain: Same case (0-100)

• Start with 50.
• Too low, but you just eliminated half the numbers!
• Now you know that 1–50 are all "too low" (You should skip all them)
• Next guess: 75.
• Too high, but again you cut down half the remaining numbers! (Skip 75 to 100)
• Next is 63 (halfway between 50 and 75).
• ...

Suppose you’re looking for a word in the dictionary. The dictionary has 240,000 words. In the worst case, how many steps do you think each search will take?

• Simple search could take 240,000 steps.
• Binary search will take 18 steps.

function binary_search<T>(list: T[], item: T): number | null {
  let low: number = 0;
  let high: number = list.length - 1;

  while (low <= high) {
    let mid: number = Math.floor((low + high) / 2);
    let guess: T = list[mid];
    if (guess === item) {
      return mid;
    }
    if (guess > item) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return null;
}

// Example usage:
const numbers = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 7;
const result = binary_search(numbers, target);
console.log(result); // Output: 3

Exercise:

Suppose you have a sorted list of 128 names, and you’re searching through it using binary search.

What’s the maximum number of steps it would take?

The maximum number of steps binary search takes can be determined using the formula:

log_2(n)

where nn is the number of elements in the list. In this case, n=128n = 128:

log_2(128) = 7

So, the maximum number of steps it would take to find a name in a sorted list of 128 names using binary search is 7 steps. 🚀

Suppose you double the size of the list. What’s the maximum number of steps now?

If you double the size of the list from 128 to 256, the maximum number of steps required by binary search is:

log_2(256) = 8

So, with 256 names, the maximum number of steps needed is 8.

This demonstrates the power of binary search—every time the list size doubles, the number of steps increases by just 1! 🚀

Big O notation

• Big O notation is special notation that tells you how fast an algorithm is.
• Big O notation lets you compare the number of operations. It tells you how fast the algorithm grows.
• Run time of algorithms is expressed in Big O notation.
• Algorithm speed isn’t measured in seconds.

![[Screenshot 2025-02-09 at 21.52.48.png]]

Some common Big O run times

Here are five Big O run times that you’ll encounter a lot, sorted from fastest to slowest:

• O(log n), also known as log time. Example: Binary search.
• O(n), also known as linear time. Example: Simple search.
• O(n * log n). Example: A fast sorting algorithm, like quicksort (coming up in chapter 4).
• O(n2). Example: A slow sorting algorithm, like selection sort (coming up in chapter 2).
• O(n!). Example: A really slow algorithm, like the traveling salesperson (coming up next!).

Salesperson problem.

1. You have a salesperson.
2. The salesperson has to go to five cities.
3. He adds up the total distance and then picks the path with the lowest distance

It’s called the traveling salesperson problem.

This is a famous problem in computer science, because its growth is appalling and some very smart people think it can’t be improved.

• There are 120 permutations with 5 cities
• It will take 120 operations to solve the problem for 5 cities.
• For 6 cities, it will take 720 operations (there are 720 permutations).
• For 7 cities, it will take 5,040 operations!