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.

Practice

1. What is the main purpose of the binary search iterative approach in a sorted array?

easy

A. To reverse the array elements

B. To find the position of a target value efficiently by repeatedly dividing the search interval in half

C. To sort the array elements in ascending order

D. To find the maximum value in the array

Solution

1. Step 1: Understand binary search goal

   Binary search aims to find a target value's position quickly in a sorted array by dividing the search space repeatedly.

2. Step 2: Identify the iterative approach

   The iterative method uses a loop to narrow down the search range until the target is found or the range is empty.

3. Final Answer:

   To find the position of a target value efficiently by repeatedly dividing the search interval in half -> Option B

4. Quick Check:

   Binary search = efficient position search [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Confusing binary search with sorting algorithms
• Thinking it works on unsorted arrays
• Assuming it finds maximum or minimum values

2. Which of the following is the correct way to initialize the mid index in an iterative binary search in JavaScript?

easy

A. const mid = Math.ceil((start + end) / 2);

B. const mid = (start + end) / 2;

C. const mid = Math.floor((start + end) / 2);

D. const mid = start + end;

Solution

1. Step 1: Understand index calculation

   Mid index must be an integer index, so we use Math.floor to round down the average of start and end.

2. Step 2: Check options for correct syntax

   const mid = Math.floor((start + end) / 2); uses Math.floor((start + end) / 2), which correctly calculates the middle index as an integer.

3. Final Answer:

   const mid = Math.floor((start + end) / 2); -> Option C

4. Quick Check:

   Mid index = Math.floor average [OK]

Hint: Use Math.floor to get integer mid index [OK]

Common Mistakes:

• Using division without floor, resulting in float index
• Using Math.ceil which can cause out-of-range index
• Adding start and end without division

3. What will be the output of the following JavaScript code?

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) start = mid + 1;
    else end = mid - 1;
  }
  return -1;
}

console.log(binarySearch([2, 4, 6, 8, 10], 6));

medium

A. 2

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace the binary search steps

   Array is [2,4,6,8,10], target is 6. Initial start=0, end=4, mid=2. arr[2] = 6 matches target.

2. Step 2: Return index when found

   Since arr[mid] equals target, function returns mid = 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value first for quick match [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in start/end updates
• Returning value instead of index

4. Identify the bug in the following iterative binary search code snippet:

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) start = mid + 1;
    else end = mid - 1;
  }
  return -1;
}

medium

A. The loop condition should be start <= end instead of start < end

B. The mid calculation should use Math.ceil instead of Math.floor

C. The function should return arr[mid] instead of mid

D. The start should be initialized to 1 instead of 0

Solution

1. Step 1: Analyze loop condition impact

   The loop uses start < end, which misses the case when start equals end, possibly skipping the last element check.

2. Step 2: Correct loop condition for full search

   Changing to start <= end ensures the loop checks all elements including when start equals end.

3. Final Answer:

   The loop condition should be start <= end instead of start < end -> Option A

4. Quick Check:

   Loop condition must include equality [OK]

Hint: Use <= to include last element in search [OK]

Common Mistakes:

• Using < excludes last element check
• Changing mid calculation unnecessarily
• Returning value instead of index

5. Given a sorted array with possible duplicate values, how can you modify the iterative binary search to find the first occurrence of a target value?

function binarySearchFirst(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  let result = -1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) {
      result = mid;
      end = mid - 1; // Continue searching left
    } else if (arr[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return result;
}

hard

A. Search right side by moving start to mid + 1 when target is found

B. Return immediately when target is found at mid

C. Change mid calculation to use Math.ceil instead of Math.floor

D. Keep track of found index and continue searching left by moving end to mid - 1

Solution

1. Step 1: Understand duplicate handling

   To find first occurrence, we must not stop at first match but continue searching left side.

2. Step 2: Use result variable and adjust end pointer

   Store current match index in result, then move end to mid - 1 to search left side for earlier occurrence.

3. Final Answer:

   Keep track of found index and continue searching left by moving end to mid - 1 -> Option D

4. Quick Check:

   Track index + search left for first occurrence [OK]

Hint: On match, move left to find first occurrence [OK]

Common Mistakes:

• Stopping search immediately on first match
• Searching right side instead of left
• Ignoring duplicates in binary search