Binary Search as Divide and Conquer in DSA Typescript - Execution Trace

Concept Flow - Binary Search as Divide and Conquer

Start with sorted array and target

↓

Calculate middle index

↓

Compare middle element with target

↓

Equal?

↓

Found

↩End Repeat Repeat

Binary search splits the sorted array in half each time, comparing the middle element to the target, then searching left or right half accordingly until found or empty.

Execution Sample

DSA Typescript

function binarySearch(arr: number[], target: number): number {
  let left = 0, 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;
}

This code searches for a target number in a sorted array by repeatedly dividing the search range in half.

Execution Table

Step	Operation	Left Index	Right Index	Middle Index	Middle Value	Comparison	Action	Array State
1	Initialize	0	6	-	-	-	Start search	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 vs 9	7 < 9, move left to mid+1	[1, 3, 5, 7, 9, 11, 13]
3	Update left	4	6	-	-	-	Search right half	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	6	5	11	11 vs 9	11 > 9, move right to mid-1	[1, 3, 5, 7, 9, 11, 13]
5	Update right	4	4	-	-	-	Search left half	[1, 3, 5, 7, 9, 11, 13]
6	Calculate mid	4	4	4	9	9 vs 9	Found target at index 4	[1, 3, 5, 7, 9, 11, 13]
7	Return	-	-	-	-	-	Return index 4	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	4	4	4	4	4
right	6	6	6	4	4	4	4
mid	-	3	-	5	-	4	-
middleValue	-	7	-	11	-	9	-

Key Moments - 3 Insights

Why do we update 'left' to mid + 1 when middle value is less than target?

Because the target cannot be at mid or any index less than mid, so we move 'left' to mid + 1 to search the right half, as shown in execution_table step 3.

Why do we stop when left > right?

When 'left' passes 'right', it means the search space is empty and the target is not found. This condition stops the loop, but in this example, the target was found before that (step 6).

Why do we calculate mid as Math.floor((left + right) / 2)?

To find the middle index between left and right, rounding down to avoid fractional index, ensuring we pick a valid array position each time (seen in steps 2, 4, 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 4?

A 4

B 3

C 5

D 6

💡 Hint

Check the 'Middle Index' column at step 4 in the execution_table.

At which step does the search range narrow to a single element?

A Step 5

B Step 6

C Step 3

D Step 2

💡 Hint

Look at 'Left Index' and 'Right Index' columns to find when they become equal.

If the target was 12 instead of 9, what would happen at step 4?

A Return index 5

B Move left to mid + 1

C Move right to mid - 1

D Return -1 immediately

💡 Hint

Compare middle value 11 with target 12 and see the action in step 4.

Concept Snapshot

Binary Search divides a sorted array by half each step.
Calculate middle index: mid = floor((left + right)/2).
Compare middle value with target.
If equal, return mid index.
If target > mid value, search right half (left = mid + 1).
If target < mid value, search left half (right = mid - 1).
Stop when left > right (target not found).

Full Transcript

Binary search is a method to find a target value in a sorted array by repeatedly dividing the search range in half. We start with left at 0 and right at the last index. We calculate the middle index and compare the middle element with the target. If they are equal, we return the middle index. If the target is greater, we move the left pointer to mid + 1 to search the right half. If the target is smaller, we move the right pointer to mid - 1 to search the left half. This process repeats until the target is found or the search range is empty (left > right). The execution table shows each step with pointer updates and comparisons, helping visualize how the search narrows down. The variable tracker shows how left, right, mid, and middle value change over time. Key moments clarify why pointers move and when the search stops. The visual quiz tests understanding of these steps.

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