Binary Search Iterative Approach in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search repeatedly divides a sorted list in half to find a target value quickly by comparing the middle element and deciding which half to search next.

beginner

In the iterative binary search, what variables are commonly used to keep track of the search range?

Two variables, usually called low and high, mark the start and end indexes of the current search range in the array.

intermediate

Why do we calculate the middle index as low + Math.floor((high - low) / 2) instead of (low + high) / 2?

Calculating middle this way prevents integer overflow when low and high are large numbers, ensuring safe and correct middle index calculation.

beginner

What condition ends the iterative binary search loop?

The loop ends when low becomes greater than high, meaning the target is not found in the array.

beginner

What is the time complexity of the binary search iterative approach and why?

The time complexity is O(log n) because the search range halves each step, quickly narrowing down the target position.

What must be true about the array for binary search to work correctly?

A The array must be sorted

B The array must contain only positive numbers

C The array must have unique elements

D The array must be unsorted

Binary search requires a sorted array to decide which half to search next.

In iterative binary search, if the middle element is less than the target, what happens next?

A Return the middle index immediately

B Search the left half by moving high

C Search the right half by moving low

D Stop the search

If middle element is less than target, the target must be in the right half, so low is moved to middle + 1.

What does the iterative binary search return if the target is not found?

A -1

B The index of the closest element

C 0

D The middle index

Returning -1 is a common way to indicate the target is not found.

Which of these is the correct way to calculate the middle index safely?

A (low + high) / 2

B low + Math.floor((high - low) / 2)

C high - low / 2

D low * high / 2

Using low + Math.floor((high - low) / 2) avoids overflow issues.

What is the main advantage of binary search over linear search?

A Works on unsorted arrays

B Simpler to implement

C Uses less memory

D Faster search time on sorted arrays

Binary search is faster because it halves the search space each step.

Explain how the iterative binary search algorithm works step-by-step.

Think about dividing the search range repeatedly.

Describe why binary search requires a sorted array and what happens if the array is not sorted.

Consider how you decide to go left or right.