Basics of Binary Search

Have you ever used a paper dictionary? Congrats! You might already know the binary Method!

Concept of Binary Method

The concept of the binary method is pretty simple, similar to find a word in a dictionary.

As we know, dictionary words are sorted alphabetically. So if you want to find words that start with the alphabet K, you won’t go through the dictionary from page one. Instead, you know it’s more efficient to start in the middle and see if the alphabet on this page ahead or behind K.

Find K in a dictionary

The binary method is efficient because it always reduces the problem size by half after one round.

Binary Search Algorithm

Binary Search is the most well-known algorithm for searching problems. It’s an algorithm based on the binary method that works repeating trying to divide problems into half of the portion in a sorted list containing the item. Just like the dictionary example above!

Let’s see how it works:

binary search logic

The key here is to check if the middle number bigger or smaller than the target. If it’s bigger, move the lower bound (left point) to the middle point. Conversely, if it’s smaller than the target, move the upper bound (right point) to the middle point.

Super cool, right? The most exciting thing about solving algorithm problems is often not writing out the program, but the process you realize there is a better way to make it work like a charm!

Let’s pause here, try to build your own binary search implementable base on this logic:

Binary Search - LeetCode

Code together

Did you have fun making your own implementation? Let’s code together anyway:

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def search(nums, target)
  # 1. handle edge case
  return -1 if nums.empty? || nums.nil?
  p1 = 0
  p2 = nums.length - 1
  # 2. condition to stop looping
  while p1 + 1 < p2
    # 3. middle calculation
    mid = p1 + (p2 - p1) / 2 
    if nums[mid] == target
      return mid
    elsif nums[mid] < target
      p1 = mid
    else
      p2 = mid
    end
  end
  # 4. target placed at left or right pointer 
  return p1 if nums[p1] == target
  return p2 if nums[p2] == target
  -1
end

There are a few things to note to implement a perfect binary search:

• Handling Edge Case — Basic input edge case handling
• When to stop the loop — Why p1 + 1 < p2 ?

You can debate that p1 < p2 or p1 ≤ p2 are workable, sometimes. However, there’s a chance you’ll end up with a dead loop if the target isn’t in the array. See example:

Binary Search dead loop

• Middle calculation — Why p1 + (p2 — p1) / 2?

In short, (p1 + p2) / 2 works when you’re using Python (or Ruby), which handles large numbers for you automatically. In Python2, operations will automatically promote intto long if int is not sufficient.

However, for C or Java, there’s a chance the sum of (p1 + p2) overflows to a negative value. You can read more in this article: Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken.

• When the target is at the left or right pointer — double-check at the end!

# 4. target placed at left or right pointer 
return p1 if nums[p1] == target
return p2 if nums[p2] == target

Time Complexity

Imagine you have eight numbers in an array. You only need three rounds to get the final result.

[1, 2, 3, 4, 5, 6, 7, 8] # find 1
round 1: [1, 2, 3, 4]
round 2: [1, 2]
round 3: [1]

Important to know that in every round, we reduce the problem size by half.

The total rounds can be calculated bylog2(8) . Let’s say you have N numbers. The worst case, total rounds will be log2(N).

Base on Big O notation theory, we called it O(log N) time complexity, and it’s way more efficient than checking every position O(n) .

If you are not familiar wiht Big O notation, try to reach out your best friend —Google!

Why need to understand the Binary method?

In modern language, binary search is usually a build-in function. So then why do I need to know the details?

You must admit that you will only write these algorithms during an interview in your life, but the important thing is that this logic and ideas will affect and inspires you far-reaching.

More Binary method Problems

• Find Minimum in Rotated Sorted Array
• first bad version
• Find First and Last Position of Element in Sorted Array
• Find K cloest elements
• Peak index in a mountain array
• Search a 2D Matrix
• Search a 2D Matrix II

Reference

How does Ruby store large numbers?

Can Integer Operations Overflow in Python?

Data Structure and Algorithms Binary Search

All images are from the author.