Binary Search as Divide and Conquer in DSA Typescript

Mental Model

Binary search splits a sorted list into halves to quickly find a target by ignoring half the list each time.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding to look in the left or right half depending on the word you want.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indexes:     [0, 1, 2, 3, 4,  5,  6]
Start -> 0 ↑
End -> 6
Mid -> 3 (value 7)

Dry Run Walkthrough

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

Goal: Find the index of target 9 using binary search

Step 1: Calculate mid index between start=0 and end=6

[1, 3, 5, 7, 9, 11, 13]
start=0, mid=3 (7), end=6

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

Step 2: Compare target 9 with mid value 7; target is greater, so move start to mid+1=4

[1, 3, 5, 7, 9, 11, 13]
start=4, end=6

Why: Since 9 > 7, target must be in the right half

Step 3: Calculate new mid index between start=4 and end=6

[1, 3, 5, 7, 9, 11, 13]
start=4, mid=5 (11), end=6

Why: Check middle of the new search range

Step 4: Compare target 9 with mid value 11; target is smaller, so move end to mid-1=4

[1, 3, 5, 7, 9, 11, 13]
start=4, end=4

Why: Since 9 < 11, target must be in the left half

Step 5: Calculate new mid index between start=4 and end=4

[1, 3, 5, 7, 9, 11, 13]
start=4, mid=4 (9), end=4

Why: Only one element left to check

Step 6: Compare target 9 with mid value 9; they are equal, return index 4

[1, 3, 5, 7, 9, 11, 13]
Found target at index 4

Why: Target found, stop searching

Result:

[1, 3, 5, 7, 9, 11, 13]
Target 9 found at index 4

Annotated Code

DSA Typescript

class BinarySearch {
  static search(arr: number[], target: number): number {
    let start = 0
    let end = arr.length - 1

    while (start <= end) {
      const mid = Math.floor((start + end) / 2) // find middle index
      if (arr[mid] === target) {
        return mid // target found
      } else if (arr[mid] < target) {
        start = mid + 1 // search right half
      } else {
        end = 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 result = BinarySearch.search(array, target)
if (result !== -1) {
  console.log(`Target ${target} found at index ${result}`)
} else {
  console.log(`Target ${target} not found`)
}

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

Calculate middle index to split array

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

Check if middle element is the target

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

If target is greater, discard left half by moving start

else { end = mid - 1 }

If target is smaller, discard right half by moving end

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 skipping half the elements each step

Edge Cases

Empty array

Returns -1 immediately since start > end

DSA Typescript

while (start <= end)

Target not in array

Search space shrinks until start > end, then returns -1

DSA Typescript

while (start <= end)

Single element array with target present

Checks the only element and returns its index

DSA Typescript

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 divides the problem in half each time, making it very fast.

Common Mistakes

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

Mistake: Not updating start or end correctly, causing infinite loop
Fix: Ensure start = mid + 1 or end = mid - 1 to shrink search space

Mistake: Using binary search on unsorted array
Fix: Sort the array first or use linear search

Summary

Binary search finds a target in a sorted list by repeatedly dividing the search range in half.

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

The key insight is that each comparison lets you ignore half the remaining elements.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. Check every element one by one until the target is found

B. Use a hash table to find the target instantly

C. Sort the list first and then search linearly

D. Repeatedly split the sorted list into halves to find the target

Solution

1. Step 1: Understand binary search principle

   Binary search works by dividing the sorted list into two halves and deciding which half to continue searching in.

2. Step 2: Compare target with middle element

   By comparing the target with the middle element, we eliminate half the list each time, making search efficient.

3. Final Answer:

   Repeatedly split the sorted list into halves to find the target -> Option D

4. Quick Check:

   Divide and conquer = split list halves [OK]

Hint: Divide sorted list in halves to find target fast [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Searching linearly instead of dividing
• Ignoring the middle element comparison

2. Which of the following is the correct TypeScript function signature for a binary search function?

easy

A. function binarySearch(arr: number[], target: number): number

B. function binarySearch(arr: number, target: number[]): number

C. function binarySearch(arr: string[], target: string): void

D. function binarySearch(arr: number[], target: number): void

Solution

1. Step 1: Identify input and output types

   Binary search takes an array of numbers and a target number, returning the index (number) or -1 if not found.

2. Step 2: Match function signature

   function binarySearch(arr: number[], target: number): number matches input types (number array and number) and returns a number index, which is correct.

3. Final Answer:

   function binarySearch(arr: number[], target: number): number -> Option A

4. Quick Check:

   Input: number[], number; Output: number [OK]

Hint: Input array and target number, output index number [OK]

Common Mistakes:

• Swapping array and target types
• Returning void instead of index
• Using wrong array element types

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

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

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

medium

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Identify array and target

   Array is [2,4,6,8,10], target is 6.

2. Step 2: Trace binary search steps

   Middle index initially is 2 (value 6), which matches target, so function returns 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Find middle index and compare target [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Returning wrong index when target found

4. Identify the bug in this binary search implementation and choose the fix:

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

medium

A. Change mid calculation to (left + right + 1) / 2

B. Change while condition to left < right

C. Change right initialization to arr.length - 1

D. Remove else if and use only if statements

Solution

1. Step 1: Check right boundary initialization

   Right should be last valid index, which is arr.length - 1, not arr.length (out of bounds).

2. Step 2: Understand impact on loop

   Using arr.length causes mid to sometimes be out of array range, causing runtime errors.

3. Final Answer:

   Change right initialization to arr.length - 1 -> Option C

4. Quick Check:

   Right boundary = last index [OK]

Hint: Right index must be last valid array index [OK]

Common Mistakes:

• Setting right to arr.length causes out-of-bounds
• Changing loop condition incorrectly
• Miscalculating mid index

5. You have a sorted array with duplicate values: [1, 2, 2, 2, 3, 4]. How would you modify binary search to find the first occurrence of 2?

hard

A. Search the right half after finding 2

B. After finding 2, continue searching left half to find earlier occurrence

C. Return the first found index immediately

D. Use linear search instead of binary search

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any matching index, not necessarily the first occurrence.

2. Step 2: Modify search to find first occurrence

   After finding target, continue searching left half to check if earlier occurrence exists, updating result accordingly.

3. Final Answer:

   After finding 2, continue searching left half to find earlier occurrence -> Option B

4. Quick Check:

   Find first occurrence by searching left side [OK]

Hint: Keep searching left after match to find first duplicate [OK]

Common Mistakes:

• Stopping at first found index
• Searching right half after match
• Switching to linear search unnecessarily