Binary Search

This section covers Binary Search, which is an efficient algorithm for searching a sorted array for a target value.

We'll focus on how to visualize the algorithm, and how visualization can help us when we are implementing the algorithm. We'll then look at some practice questions involving Binary Search.

The classic Binary Search algorithm is used to search for a target value in a sorted array.

DESCRIPTION

Given a sorted array of integers nums and a target value target, write a function to determine if target is in the array. If target is present in the array, return its index. Otherwise, return -1.

Example 1:

Input:

nums = [-1,0,3,5,9,12], target = 9

Output: 4 (nums[4] = 9)

Example 2:

Input:

nums = [-1,0,3,5,9,12], target = 2

Output: -1 (2 is not in the array, so we return -1.)

The appeal of Binary Search is readily apparent when we compare it to the brute-force approach.

The graphic below shows how the brute-force approach searches the sorted array for the target value 6. The elements considered during the search are highlighted in darker color.

Compare that to Binary Search, which locates 6 after only 3 "steps":

These two graphics show the efficiency of Binary Search, which performs the search in O(log n) time, compared to the much slower O(n) time of the Brute-Force Approach.

Intuition

Binary Search is efficient because it repeatedly cuts the portion of the array that needs to be searched in half.

Some of the visuals below are animated. Click on the to the left of each visual to start the animation.

Binary Search works because our array is sorted, and the middle element of a sorted array is a great starting point. All the elements to the left of the middle element are smaller than or equal to it, and all the elements to the right are larger than or equal to it.

Let's say our target is 6.

Since our target is greater than the middle element, we can safely ignore the left half of the array - we know the target is not there. We indicate this in the visual by turning those elements gray.

This leaves the right half of the array to search, and we've cut the search space in half for the first time.

target = 6

How do we search the right half? With the same approach! We take the middle element of the right half (8), and compare it to the target.

Since our target is less than the middle element, we can now ignore the right half of the updated search space. We've just cut the search space in half again!

target = 6

Now our search space has only two elements. By convention, we choose the first of these two elements as the "middle". Our target is equal to the middle element, meaning we've found it!

target = 6

Key Takeaway

Binary Search works by repeatedly cutting the relevant search space of the array in half, until it either finds the target or the search space is empty, at which point it concludes that the target is not in the array. The halving is where the algorithm gets its O(log n) time complexity.

Implementation

Variables

Before diving into the code, let's first learn what each variable represents in the Binary Search algorithm, and visualize how they change during the search.

For these visualizations, target = 6 and nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

Initialize two pointers, left and right, to the start and end of the array, respectively. These two pointers represent the search space of the array. Since the entire search space is valid, they are shown in green.

target = 6

Next, we iteratively halve the search space until we've either found the target or the search space is empty (we will learn how to visualize this in the next section).

So while left <= right:

Initialize a pointer mid = (left + right) // 2. mid represents the middle of the current search space, as well as the element that we compare to target.

target = 6

Note: The // operator is used for integer division in Python. For example, in the visual above, 9 // 2 = 4.

This means that mid is always an integer, and will be the first of the two possible middle elements if the search space has an even number of elements.

Compare the element at mid to the target. In this case, target > nums[mid], so we drop the left half of the search space by updating left = mid + 1. The elements that have been dropped are shown in gray.

target = 6

At this point, left and right reflect the updated search space. So set mid = (left + right) // 2 again, and repeat the process until either nums[mid] == target or left > right.

target = 6

Code

Let's see the code!


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 6

0 / 7

Edge Cases

To deepen our understanding of Binary Search, let's consider some edge cases:

Empty Array

If the input array is empty, left starts at 0, right starts at -1, and the loop will not run, and we will return -1.

target = 2, nums = []


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 2

0 / 2

Single Element Array

If the input array has only one element, left, mid, and right will all be the same, and the loop will run once. If the single element is the target, we return its index. Otherwise, left > right, so we exit the loop and return -1.

target = 2, nums = [1]


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 2

0 / 4

Target Not in Array

If the target is not in the array, left will eventually be greater than right, and we will return -1.

target = 2, nums = [1, 3, 4, 8]


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 2

0 / 6

This example helps us visualize the termination condition of Binary Search.

When left = right, as shown below, there is still one element in the search space, highlighted in green.

However, when left > right, as shown below, the search space is empty, and we know that the target is not in the array. We can visualize the binary search algorithm stopping when the left pointer "passes" the right pointer.

These visualizations should help you internalize why the condition left <= right is used in the Binary Search algorithm - once left overtakes right, the search space is empty and we know that the target is not in the array.

Complexity Analysis

Time Complexity: O(log n), since we are halving the search space at each step. n is the number of elements in the input array.

Space Complexity: O(1), since we are using a constant amount of space for the pointers, regardless of the size of the input array.

Summary

Binary Search is an effective algorithm because it allows us to repeatedly cut our search space in half until we find the target or conclude that it is not in the array. In other words, during each iteration of the algorithm, we are able to discard half of the search space.

Here are some problems that also use this concept of repeatedly discarding half of the search space:

Question	Difficulty
Apple Harvest (Koko Eating Bananas)	Medium
Search in Rotated Sorted Array	Medium

Next: Apple Harvest (Koko Eating Bananas)

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Linked List: Swap Nodes in Pairs

Apple Harvest (Koko Eating Bananas)

Binary Search

This section covers Binary Search, which is an efficient algorithm for searching a sorted array for a target value.

We'll focus on how to visualize the algorithm, and how visualization can help us when we are implementing the algorithm. We'll then look at some practice questions involving Binary Search.

The classic Binary Search algorithm is used to search for a target value in a sorted array.

DESCRIPTION

Example 1:

Input:

nums = [-1,0,3,5,9,12], target = 9

Output: 4 (nums[4] = 9)

Example 2:

Input:

nums = [-1,0,3,5,9,12], target = 2

Output: -1 (2 is not in the array, so we return -1.)

The appeal of Binary Search is readily apparent when we compare it to the brute-force approach.

The graphic below shows how the brute-force approach searches the sorted array for the target value 6. The elements considered during the search are highlighted in darker color.

Compare that to Binary Search, which locates 6 after only 3 "steps":

These two graphics show the efficiency of Binary Search, which performs the search in O(log n) time, compared to the much slower O(n) time of the Brute-Force Approach.

Intuition

Binary Search is efficient because it repeatedly cuts the portion of the array that needs to be searched in half.

Some of the visuals below are animated. Click on the to the left of each visual to start the animation.

Let's say our target is 6.

This leaves the right half of the array to search, and we've cut the search space in half for the first time.

target = 6

How do we search the right half? With the same approach! We take the middle element of the right half (8), and compare it to the target.

Since our target is less than the middle element, we can now ignore the right half of the updated search space. We've just cut the search space in half again!

target = 6

Now our search space has only two elements. By convention, we choose the first of these two elements as the "middle". Our target is equal to the middle element, meaning we've found it!

target = 6

Key Takeaway

Implementation

Variables

Before diving into the code, let's first learn what each variable represents in the Binary Search algorithm, and visualize how they change during the search.

For these visualizations, target = 6 and nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

Initialize two pointers, left and right, to the start and end of the array, respectively. These two pointers represent the search space of the array. Since the entire search space is valid, they are shown in green.

target = 6

Next, we iteratively halve the search space until we've either found the target or the search space is empty (we will learn how to visualize this in the next section).

So while left <= right:

Initialize a pointer mid = (left + right) // 2. mid represents the middle of the current search space, as well as the element that we compare to target.

target = 6

Note: The // operator is used for integer division in Python. For example, in the visual above, 9 // 2 = 4.

This means that mid is always an integer, and will be the first of the two possible middle elements if the search space has an even number of elements.

Compare the element at mid to the target. In this case, target > nums[mid], so we drop the left half of the search space by updating left = mid + 1. The elements that have been dropped are shown in gray.

target = 6

At this point, left and right reflect the updated search space. So set mid = (left + right) // 2 again, and repeat the process until either nums[mid] == target or left > right.

target = 6

Code

Let's see the code!


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 6

0 / 7

Edge Cases

To deepen our understanding of Binary Search, let's consider some edge cases:

Empty Array

If the input array is empty, left starts at 0, right starts at -1, and the loop will not run, and we will return -1.

target = 2, nums = []


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 2

0 / 2

Single Element Array

target = 2, nums = [1]


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 2

0 / 4

Target Not in Array

If the target is not in the array, left will eventually be greater than right, and we will return -1.

target = 2, nums = [1, 3, 4, 8]


def binary_search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1

binary search for 2

0 / 6

This example helps us visualize the termination condition of Binary Search.

When left = right, as shown below, there is still one element in the search space, highlighted in green.

Complexity Analysis

Time Complexity: O(log n), since we are halving the search space at each step. n is the number of elements in the input array.

Space Complexity: O(1), since we are using a constant amount of space for the pointers, regardless of the size of the input array.

Summary

Here are some problems that also use this concept of repeatedly discarding half of the search space:

Question	Difficulty
Apple Harvest (Koko Eating Bananas)	Medium
Search in Rotated Sorted Array	Medium

Next: Apple Harvest (Koko Eating Bananas)

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103