Binary Search - AP Computer Science Principles

Determine the middle index for 'low' = 2, 'high' = 6.

Middle index = 4. Using the formula $(2 + 6) / 2 = 4$ .
What kind of search is binary search considered?

A logarithmic search. Uses logarithmic time complexity for efficient searching.
How does binary search improve efficiency compared to linear search?

By halving the search range each step. Eliminates half the possibilities with each comparison.
In binary search, what happens if 'low' equals 'high'?

Check the element at 'low' or 'high'. Single element left to verify as target match.
Identify a situation where binary search cannot be applied.

On an unsorted dataset. Binary search assumes sorted order to function correctly.
Is binary search applicable to all data types?

Yes, if they are comparable and sorted. Elements must support comparison operators and ordering.
What is the effect of binary search on a dataset with duplicate elements?

Finds one occurrence of the target. Standard behavior returns first match found, not all.
Does binary search require additional memory for its operations?

No, uses constant space $O(1)$ . Only needs variables for indices, not extra arrays.
What happens if the target is less than the middle element in binary search?

Search the left half of the dataset. Target must be in the smaller half of the remaining elements.
What is returned if the target element is not found in binary search?

Typically, -1 or null. Standard convention to indicate search failure.
Find the new middle index if low = 0 and high = 8 in binary search.

Middle index = 4. Using the formula $(0 + 8) / 2 = 4$ .
What is the effect of binary search on a dataset of size 1?

Directly checks the only element. One comparison determines if target is found.
What is one advantage of binary search over linear search?

Faster on sorted datasets. Logarithmic vs linear time complexity provides significant speedup.
What is an iterative approach to implementing binary search?

Using a while loop to adjust 'low' and 'high'. Uses loops to repeatedly narrow the search boundaries.
What happens if the middle element equals the target in binary search?

Returns the middle index. Successful match terminates search with target location.
Which data structure is most suitable for binary search?

Sorted array or list. Allows constant-time access to any index for comparisons.
Which programming concept is often used with binary search?

Recursion or iterative loops. Essential for implementing the divide-and-conquer strategy.
Is binary search suitable for recursive implementation?

Yes, it can be implemented recursively. Natural fit for divide-and-conquer recursive approach.
What is the impact of binary search on unsorted data?

It fails to find elements reliably. Ordering assumption is violated, breaking the algorithm.
Which condition ends a binary search loop?

When 'low' exceeds 'high'. Indicates no valid search range remains.
Calculate the middle index for 'low' = 3 and 'high' = 7.

Middle index = 5. Using the formula $(3 + 7) / 2 = 5$ .
What is the role of the 'low' and 'high' pointers in binary search?

They define the current search range. Boundaries that shrink with each iteration until target found.
What is a potential drawback of using binary search?

Requires a sorted dataset. Limits use to pre-sorted data structures only.
How does binary search behave on a single-element dataset?

Checks if the element is the target. Performs one comparison to determine success or failure.
What is a key difference between binary and linear search?

Binary requires sorting; linear does not. Binary needs preprocessing while linear works on any order.
What is a practical limitation of binary search?

Requires static datasets. Cannot handle dynamic insertions or deletions efficiently.
Determine the new search range if binary search finds the target.

Search ends; no new range is needed. Target found means search is complete and successful.
How does binary search handle an empty dataset?

Returns -1 or null immediately. No elements exist to search through.
Why is binary search not suitable for datasets with frequent updates?

Frequent sorting is required. Maintaining sorted order becomes costly with many changes.
For binary search, what is the typical return value for a successful search?

The index of the target element. Provides the location where the target was found.
State the time complexity of binary search in the worst case.

$O(\text{log } n)$ . Eliminates half the search space with each comparison.
In binary search, if the target is greater than the middle element, what is the next step?

Search the right half of the dataset. Target must be in the larger half of the remaining elements.
Does binary search work on linked lists?

Not efficiently due to non-constant time access. Sequential access makes random indexing inefficient.
State the average time complexity of binary search.

$O(\text{log } n)$ . Consistently eliminates half the search space each iteration.
Which algorithmic paradigm does binary search belong to?

Divide and conquer. Repeatedly divides the problem into smaller subproblems.
How does binary search determine the middle element of the dataset?

Middle index = $\frac{\text{low} + \text{high}}{2}$ . Formula calculates the midpoint between current boundaries.
What is a common application of binary search in computer science?

Searching in databases. Efficiently locates records in sorted database indexes.
What is the space complexity of binary search?

$O(1)$ . Only uses a few variables regardless of dataset size.
Identify the first step in performing a binary search.

Calculate the middle index of the dataset. Starting point to compare against the target value.
What is the primary requirement for applying binary search on a dataset?

The dataset must be sorted. Binary search relies on ordering to eliminate half the search space.

Study these flashcards