Binary Search Iterative Approach in DSA Javascript

Mental Model

Binary search finds a number by repeatedly cutting the search area in half until the number is found or no area remains.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if you should look in the left or right half, and repeating this until you find the word.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers:  low ↑                 high ↑
Middle:           mid ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], search for 9

Goal: Find the index of 9 in the array using iterative binary search

Step 1: Calculate mid index between low=0 and high=6

Array: 1 -> 3 -> 5 -> [7] -> 9 -> 11 -> 13
Indexes: 0    1    2    3    4    5    6
Pointers: low=0 ↑          mid=3 ↑          high=6 ↑

Why: We check the middle element to decide which half to search next

Step 2: Compare mid value 7 with target 9; 7 < 9, so move low to mid+1=4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13
Indexes: 0    1    2    3    4    5    6
Pointers:           low=4 ↑    high=6 ↑

Why: Since 7 is less than 9, the target must be in the right half

Step 3: Calculate mid index between low=4 and high=6

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13
Indexes: 0    1    2    3    4    5    6
Pointers:           low=4 ↑    mid=5 ↑    high=6 ↑

Why: Find new middle to check in the narrowed search area

Step 4: Compare mid value 11 with target 9; 11 > 9, so move high to mid-1=4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13
Indexes: 0    1    2    3    4    5    6
Pointers:           low=4 ↑    high=4 ↑

Why: Since 11 is greater than 9, the target must be in the left half

Step 5: Calculate mid index between low=4 and high=4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13
Indexes: 0    1    2    3    4    5    6
Pointers:           low=4 ↑    mid=4 ↑    high=4 ↑

Why: When low equals high, check the single remaining element

Step 6: Compare mid value 9 with target 9; found target at index 4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13
Indexes: 0    1    2    3    4    5    6
Pointers:           found at mid=4 ↑

Why: Target found, stop searching

Result:

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13
Target 9 found at index 4

Annotated Code

DSA Javascript

class BinarySearch {
  static search(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
      const mid = Math.floor((low + high) / 2); // find middle index
      if (arr[mid] === target) {
        return mid; // target found
      } else if (arr[mid] < target) {
        low = mid + 1; // search right half
      } else {
        high = mid - 1; // search left half
      }
    }
    return -1; // target not found
  }
}

// Driver code
const array = [1, 3, 5, 7, 9, 11, 13];
const target = 9;
const index = BinarySearch.search(array, target);
if (index !== -1) {
  console.log(`Target ${target} found at index ${index}`);
} else {
  console.log(`Target ${target} not found in array`);
}

const mid = Math.floor((low + high) / 2); // find middle index

calculate middle index to split search area

if (arr[mid] === target) { return mid; }

check if middle element is the target

else if (arr[mid] < target) { low = mid + 1; }

if middle element less than target, search right half

else { high = mid - 1; }

if middle element greater than target, search left half

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space until the target is found or space is empty

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by reducing search steps exponentially

Edge Cases

empty array

returns -1 immediately because low > high

DSA Javascript

while (low <= high) {

target smaller than all elements

search narrows and returns -1 after checking all possibilities

DSA Javascript

while (low <= high) {

target larger than all elements

search narrows and returns -1 after checking all possibilities

DSA Javascript

while (low <= high) {

target is first element

found quickly when mid points to first element

DSA Javascript

if (arr[mid] === target) { return mid; }

target is last element

found quickly when mid points to last element

DSA Javascript

if (arr[mid] === target) { return mid; }

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it cuts the search space in half each step.

Common Mistakes

Mistake: Using 'low < high' instead of 'low <= high' in the loop condition
Fix: Change loop condition to 'while (low <= high)' to include the case when low equals high

Mistake: Calculating mid as (low + high) / 2 without floor, causing mid to be a float
Fix: Use Math.floor((low + high) / 2) to get an integer index

Mistake: Not updating low or high correctly, causing infinite loop
Fix: Ensure low = mid + 1 when target is greater, and high = mid - 1 when target is smaller

Summary

Finds the position of a target value in a sorted array by repeatedly halving the search range.

Use when you have a sorted list and want to find an element efficiently.

The key insight is to compare the middle element and discard half the list each time.