Binary Search Iterative Approach in DSA Javascript - 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: low (start index) and high (end index) define the current search range within the sorted array.

intermediate

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

To avoid potential overflow when low and high are large numbers, this formula safely calculates the middle index without exceeding number limits.

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 space halves with each step, quickly narrowing down the target position.

What must be true about the array before applying binary search?

A The array must be unsorted

B The array must be sorted

C The array must contain only positive numbers

D The array must have unique elements only

Binary search only works correctly on sorted arrays because it relies on order to decide which half to search.

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

A Search the left half by moving high

B Stop the search and return -1

C Search the right half by moving low

D Return the middle index immediately

If middle element is less than target, the target must be in the right half, so low is moved to mid + 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 null

Returning -1 is a common way to indicate the target is not present in the array.

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

A mid = (low + high) / 2

B mid = (low - high) / 2

C mid = high - low

D mid = low + Math.floor((high - low) / 2)

Calculating mid as low + Math.floor((high - low) / 2) prevents overflow when low and high are large.

What is the best description of the binary search algorithm?

A Divide and conquer by halving the search space

B Linear search through all elements

C Randomly pick elements until found

D Sort the array then search linearly

Binary search uses divide and conquer by halving the search space each step.

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

Think about how you cut the search space in half each time.

Describe why binary search is faster than linear search on sorted arrays.

Focus on how many elements you check in each method.