Binary Search

Mix.install([
  {:kino, github: "livebook-dev/kino", override: true},
  {:kino_lab, "~> 0.1.0-dev", github: "jonatanklosko/kino_lab"},
  {:vega_lite, "~> 0.1.4"},
  {:kino_vega_lite, "~> 0.1.1"},
  {:benchee, "~> 0.1"},
  {:ecto, "~> 3.7"},
  {:math, "~> 0.7.0"},
  {:faker, "~> 0.17.0"},
  {:utils, path: "#{__DIR__}/../utils"},
  {:tested_cell, git: "https://github.com/BrooklinJazz/tested_cell"}
])

Navigation

Return Home Report An Issue

Setup

Ensure you type the ea keyboard shortcut to evaluate all Elixir cells before starting. Alternatively you can evaluate the Elixir cells as you read.

Binary Search

Binary search is a type of sorting algorithm. It’s part of a family of algorithms known as Divide and Conquer algorithms.

Divide and conquer algorithms work by dividing the computer needs to do into parts.

Often, they split some group of elements into two parts, and then further split those halves into more two parts.

flowchart
a[Collection]
b1[Left Half]
b2[Right Half]
c1[Left Half]
c2[Left Half]
c3[Right Half]
c4[Left Half]

a --> b1
a --> b2
b1 --> c1
b1 --> c2
b2 --> c3
b2 --> c4

Let’s say we want to find the number 5 in a sorted tuple, but we don’t know it’s index. Binary search works by finding the mid point in the tuple, then checking if the mid point is higher or lower than the desired number.

flowchart LR
a[1]
b[2]
c[3]
d[4]
e[5]
a --> b --> c --> d --> e
style c fill: yellow

We repeat this process of halving the number of elements to check, then finding the mid point to halve it again until we find the desired element.

flowchart LR
  d[4]
  e[5]

  d --> e
  style d fill: yellow

This leaves us with a single element left to check, and it matches our desired element.

flowchart LR
5
style 5 fill: lightgreen

You can watch this video on binary search by HackerRank for an in depth guide to how that works.

Now you might wonder, how useful? It’s a fair question. Not many programming jobs will require vast knowledge of DSA (Domain Structures and Algorithms). Some jobs do use them for interview questions, however realistically if you ever needed an algorithm, you could simply look up an implementation or use an existing library.

However, divide and conquer is useful for more than just finding elements in a collection. It’s a mindset that can save you time every single day.

For example, if your code is crashing or causing an error, you can debug it using binary search.

In addition, presently if you wanted to find an element with an unknown index in a tuple, it could be challenging. Instead, you might convert it to a list, but this is expensive, or at least it’s $O(n)$ complexity at best.

large_tuple = 1..10_000_000 |> Enum.to_list() |> List.to_tuple()

Enum.find(Tuple.to_list(large_tuple), fn each -> each === 9_987_000 end)

Instead, binary search halves the number of elements to search with each run. At first you have $n$ elements to search, then $n/2$ elements, then $n/4$ elements, and so on. That means it has $O(log n)$ complexity.

Utils.graph(:binary_search)

In the Elixir cell below, create a binary search algorithm that finds the index of a given value in a sorted tuple.

tuple = 1..100 |> Enum.to_list() |> List.to_tuple()

Binary.search(tuple, 1)
0

Binary.search(tuple, 50)
49

Binary.search(tuple, 100)
99

defmodule Binary do
  def search(tuple, element) do
  end
end

Binary.search(large_tuple, 9_987_000)

Commit Your Progress

Run the following in your command line from the project folder to track and save your progress in a Git commit.

$ git add .
$ git commit -m "finish binary search exercise"