Get Premium
Binary Search

Binary Search Overview

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.
PRIMARY.lightlinearbinary-search12345678910binary-search12345678910binary-search12345678910binary-search12345678910binary-search12345678910binary-search12345678910
Compare that to Binary Search, which locates 6 after only 3 "steps":
PRIMARY.lightbinary-searchbinary-search12345678910binary-search12345678910binary-search12345678910
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 play button 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.
123456789100123456789
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.
123456789100123456789
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!
123456789100123456789
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!
123456789100123456789
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.
123456789100123456789
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.
123456789100123456789leftright
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.
13480123leftrightmid
  • 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.
123456789100123456789leftrightmid
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.
    123456789100123456789leftrightmid
    target = 6

Code

Let's see the code!
Visualization
Try these examples:
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
123456789100123456789

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 = []
Visualization
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]
Visualization
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
10

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]
Visualization
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
13480123

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.
13480123leftrightmid
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.
13480123leftrightmid
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.
Test Your Knowledge

Login to take the complexity quiz and track your progress

Complexity Analysis

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

Space Complexity: O(1) 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:
DoneQuestionDifficulty
Apple Harvest (Koko Eating Bananas)
Medium
Search in Rotated Sorted Array
Medium
Split Array Largest Sum
Hard
Kth Smallest Element in a Sorted Matrix
Medium
Minimum Shipping Capacity (with Weight Constraints)
Hard
Mark as read
Next: Apple Harvest (Koko Eating Bananas)

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

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsAnthropic SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift PremiumHello Interview Premium
Legal
Terms and ConditionsPrivacy PolicySecurity
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.

Binary Search Overview | Hello Interview