Binary Search in Array - Iteration - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given a sorted array of integers and a target number. Your task is to find the index of the target number using the binary search algorithm, implemented in an iterative way (using loops instead of recursion).

Binary search works only when the array is sorted in ascending order. If the target exists in the array, return its index. Otherwise, return -1.

Examples❯

Input Array Target Output Description
[10, 20, 30, 40, 50] 30 2 Target 30 is at index 2
[5, 10, 15, 20, 25] 5 0 First element match
[5, 10, 15, 20, 25] 25 4 Last element match
[1, 3, 5, 7, 9] 6 -1 6 does not exist in the array
[2, 4, 6, 8, 10] 11 -1 Target is greater than all elements
[2, 4, 6, 8, 10] 1 -1 Target is smaller than all elements
[] 10 -1 Empty array, nothing to search
[100] 100 0 Single element match
[100] 200 -1 Single element does not match

Solution❯

Step-by-Step Understanding of Binary Search

Before diving into code, let’s first understand what binary search is trying to solve.

Imagine you have a sorted array of numbers, and you're trying to find the index of a particular number (called the target). Instead of checking each number one by one, which can be slow, binary search helps you find the number much faster—by always checking the middle of the current search range and cutting the problem in half at each step.

This method is extremely efficient, with a time complexity of O(log n), making it ideal for searching in large sorted arrays.

Example Problem

Let’s say we are given the sorted array: [2, 4, 6, 8, 10, 12, 14] and we are asked to find the index of the number 10.

Step-by-Step Execution

  1. We start with two pointers:
    • low = 0 (start of the array)
    • high = 6 (end of the array)
  2. Calculate mid index: mid = Math.floor((0 + 6) / 2) = 3
  3. Check the middle element: arr[3] = 8
  4. Since 8 < 10, the target must be in the right half, so we set low = mid + 1 = 4
  5. Now, low = 4, high = 6. Calculate new mid: mid = Math.floor((4 + 6) / 2) = 5
  6. Check arr[5] = 12. Since 12 > 10, we now look in the left half: high = mid - 1 = 4
  7. Now, low = 4 and high = 4. So, mid = 4
  8. arr[4] = 10 which is the target! Return index 4

How the Algorithm Works

  • Keep narrowing the range between low and high
  • Each time, compare the middle element to the target
  • If it's a match, return the index
  • If the target is smaller, search in the left half
  • If the target is larger, search in the right half
  • Repeat until low exceeds high

Handling Edge Cases

  • Target not in the array: Eventually, low > high, and we return -1
  • Target smaller than all elements: First mid will already be greater, and we keep moving left until no elements are left
  • Target greater than all elements: Mid will always be smaller, we keep moving right until no elements are left
  • Empty array: Since low = 0 and high = -1 initially, the loop doesn't run and we return -1
  • Single element array:
    • If it matches the target → return index 0
    • If not → return -1

Finally

Binary search is one of the most efficient algorithms for searching in sorted arrays. It’s important to carefully manage the low and high pointers and always check for edge cases like empty arrays or off-bound conditions. Once mastered, binary search becomes a powerful tool in your problem-solving toolkit.

Algorithm Steps❯

  1. Given a sorted array arr and a target value.
  2. Initialize two pointers: low = 0 and high = arr.length - 1.
  3. Repeat while low ≤ high:
  4. → Calculate mid = Math.floor((low + high) / 2).
  5. → If arr[mid] == target, return mid (target found).
  6. → If arr[mid] < target, set low = mid + 1.
  7. → Else, set high = mid - 1.
  8. If the loop ends without finding the target, return -1 (not found).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
  int low = 0, high = size - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

int main() {
  int arr[] = {1, 3, 5, 7, 9, 11};
  int size = sizeof(arr) / sizeof(arr[0]);
  int target = 7;
  printf("Index: %d\n", binarySearch(arr, size, target));
  return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The target element is found at the middle index on the first comparison.
Average CaseO(log n)The search space is divided in half during each iteration until the target is found or determined to be absent.
Worst CaseO(log n)The target is located at the very beginning or end, or is not in the array, requiring the full depth of the binary search process.

Space Complexity❯

O(1)

Explanation: The algorithm uses constant space. It only maintains a few variables (like low, high, and mid) and does not allocate extra space based on input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...