AP Computer Science Principles Flashcards: Binary Search

What this deck covers

This deck focuses on Binary Search, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science Principles.

How to use these flashcards

Work through these flashcards in short sessions. Try to answer each prompt before flipping the card, then revisit any cards you miss until the explanation feels automatic.

Flashcard 1: What happens if the middle element equals the target in binary search?

Answer: Returns the middle index. Successful match terminates search with target location.

Flashcard 2: Which algorithmic paradigm does binary search belong to?

Answer: Divide and conquer. Repeatedly divides the problem into smaller subproblems.

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

Answer: Middle index = 4. Using the formula $(2 + 6) / 2 = 4$.

Flashcard 4: What is a common application of binary search in computer science?

Answer: Searching in databases. Efficiently locates records in sorted database indexes.

Flashcard 5: What kind of search is binary search considered?

Answer: A logarithmic search. Uses logarithmic time complexity for efficient searching.

Flashcard 6: State the time complexity of binary search in the worst case.

Answer: $O(\text{log } n)$. Eliminates half the search space with each comparison.

Flashcard 7: How does binary search improve efficiency compared to linear search?

Answer: By halving the search range each step. Eliminates half the possibilities with each comparison.

Flashcard 8: How does binary search behave on a single-element dataset?

Answer: Checks if the element is the target. Performs one comparison to determine success or failure.

Flashcard 9: In binary search, what happens if 'low' equals 'high'?

Answer: Check the element at 'low' or 'high'. Single element left to verify as target match.

Flashcard 10: What is the space complexity of binary search?

Answer: $O(1)$. Only uses a few variables regardless of dataset size.

Flashcard 11: Identify a situation where binary search cannot be applied.

Answer: On an unsorted dataset. Binary search assumes sorted order to function correctly.

Flashcard 12: Is binary search applicable to all data types?

Answer: Yes, if they are comparable and sorted. Elements must support comparison operators and ordering.

Flashcard 13: What is the effect of binary search on a dataset with duplicate elements?

Answer: Finds one occurrence of the target. Standard behavior returns first match found, not all.

Flashcard 14: Does binary search require additional memory for its operations?

Answer: No, uses constant space $O(1)$. Only needs variables for indices, not extra arrays.

Flashcard 15: What happens if the target is less than the middle element in binary search?

Answer: Search the left half of the dataset. Target must be in the smaller half of the remaining elements.

Flashcard 16: In binary search, if the target is greater than the middle element, what is the next step?

Answer: Search the right half of the dataset. Target must be in the larger half of the remaining elements.

Flashcard 17: What is the role of the 'low' and 'high' pointers in binary search?

Answer: They define the current search range. Boundaries that shrink with each iteration until target found.

Flashcard 18: What is the effect of binary search on a dataset of size 1?

Answer: Directly checks the only element. One comparison determines if target is found.

Flashcard 19: How does binary search improve efficiency compared to linear search?

Answer: By halving the search range each step. Eliminates half the possibilities with each comparison.

Flashcard 20: What is returned if the target element is not found in binary search?

Answer: Typically, -1 or null. Standard convention to indicate search failure.

Flashcard 21: Find the new middle index if low = 0 and high = 8 in binary search.

Answer: Middle index = 4. Using the formula $(0 + 8) / 2 = 4$.

Flashcard 22: Determine the new search range if binary search finds the target.

Answer: Search ends; no new range is needed. Target found means search is complete and successful.

Flashcard 23: What is the effect of binary search on a dataset of size 1?

Answer: Directly checks the only element. One comparison determines if target is found.

Flashcard 24: Does binary search work on linked lists?

Answer: Not efficiently due to non-constant time access. Sequential access makes random indexing inefficient.

Flashcard 25: What is one advantage of binary search over linear search?

Answer: Faster on sorted datasets. Logarithmic vs linear time complexity provides significant speedup.

Flashcard 26: What is an iterative approach to implementing binary search?

Answer: Using a while loop to adjust 'low' and 'high'. Uses loops to repeatedly narrow the search boundaries.

Flashcard 27: What happens if the middle element equals the target in binary search?

Answer: Returns the middle index. Successful match terminates search with target location.

Flashcard 28: Which data structure is most suitable for binary search?

Answer: Sorted array or list. Allows constant-time access to any index for comparisons.

Flashcard 29: Which data structure is most suitable for binary search?

Answer: Sorted array or list. Allows constant-time access to any index for comparisons.

Flashcard 30: Which condition ends a binary search loop?

Answer: When 'low' exceeds 'high'. Indicates no valid search range remains.

Flashcard 31: What is one advantage of binary search over linear search?

Answer: Faster on sorted datasets. Logarithmic vs linear time complexity provides significant speedup.

Flashcard 32: Calculate the middle index for 'low' = 3 and 'high' = 7.

Answer: Middle index = 5. Using the formula $(3 + 7) / 2 = 5$.

Flashcard 33: What is a practical limitation of binary search?

Answer: Requires static datasets. Cannot handle dynamic insertions or deletions efficiently.

Flashcard 34: What kind of search is binary search considered?

Answer: A logarithmic search. Uses logarithmic time complexity for efficient searching.

Flashcard 35: What is returned if the target element is not found in binary search?

Answer: Typically, -1 or null. Standard convention to indicate search failure.

Flashcard 36: Find the new middle index if low = 0 and high = 8 in binary search.

Answer: Middle index = 4. Using the formula $(0 + 8) / 2 = 4$.

Flashcard 37: What happens if the target is less than the middle element in binary search?

Answer: Search the left half of the dataset. Target must be in the smaller half of the remaining elements.

Flashcard 38: What is a key difference between binary and linear search?

Answer: Binary requires sorting; linear does not. Binary needs preprocessing while linear works on any order.

Flashcard 39: What is a potential drawback of using binary search?

Answer: Requires a sorted dataset. Limits use to pre-sorted data structures only.

Flashcard 40: Which programming concept is often used with binary search?

Answer: Recursion or iterative loops. Essential for implementing the divide-and-conquer strategy.

Flashcard 41: Is binary search suitable for recursive implementation?

Answer: Yes, it can be implemented recursively. Natural fit for divide-and-conquer recursive approach.

Flashcard 42: What is the impact of binary search on unsorted data?

Answer: It fails to find elements reliably. Ordering assumption is violated, breaking the algorithm.

Flashcard 43: How does binary search handle an empty dataset?

Answer: Returns -1 or null immediately. No elements exist to search through.

Flashcard 44: Which programming concept is often used with binary search?

Answer: Recursion or iterative loops. Essential for implementing the divide-and-conquer strategy.

Flashcard 45: Identify a situation where binary search cannot be applied.

Answer: On an unsorted dataset. Binary search assumes sorted order to function correctly.

Flashcard 46: Which condition ends a binary search loop?

Answer: When 'low' exceeds 'high'. Indicates no valid search range remains.

Flashcard 47: Calculate the middle index for 'low' = 3 and 'high' = 7.

Answer: Middle index = 5. Using the formula $(3 + 7) / 2 = 5$.

Flashcard 48: How does binary search determine the middle element of the dataset?

Answer: Middle index = $\frac{\text{low} + \text{high}}{2}$. Formula calculates the midpoint between current boundaries.

Flashcard 49: What is the role of the 'low' and 'high' pointers in binary search?

Answer: They define the current search range. Boundaries that shrink with each iteration until target found.

Flashcard 50: State the average time complexity of binary search.

Answer: $O(\text{log } n)$. Consistently eliminates half the search space each iteration.

Flashcard 51: What is the primary requirement for applying binary search on a dataset?

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

Flashcard 52: Is binary search applicable to all data types?

Answer: Yes, if they are comparable and sorted. Elements must support comparison operators and ordering.

Flashcard 53: What is a potential drawback of using binary search?

Answer: Requires a sorted dataset. Limits use to pre-sorted data structures only.

Flashcard 54: How does binary search behave on a single-element dataset?

Answer: Checks if the element is the target. Performs one comparison to determine success or failure.

Flashcard 55: What is the impact of binary search on unsorted data?

Answer: It fails to find elements reliably. Ordering assumption is violated, breaking the algorithm.

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

Answer: Middle index = 4. Using the formula $(2 + 6) / 2 = 4$.

Flashcard 57: What is a key difference between binary and linear search?

Answer: Binary requires sorting; linear does not. Binary needs preprocessing while linear works on any order.

Flashcard 58: Is binary search suitable for recursive implementation?

Answer: Yes, it can be implemented recursively. Natural fit for divide-and-conquer recursive approach.

Flashcard 59: What is a practical limitation of binary search?

Answer: Requires static datasets. Cannot handle dynamic insertions or deletions efficiently.

Flashcard 60: Determine the new search range if binary search finds the target.

Answer: Search ends; no new range is needed. Target found means search is complete and successful.

Flashcard 61: How does binary search handle an empty dataset?

Answer: Returns -1 or null immediately. No elements exist to search through.

Flashcard 62: For binary search, what is the typical return value for a successful search?

Answer: The index of the target element. Provides the location where the target was found.

Flashcard 63: Why is binary search not suitable for datasets with frequent updates?

Answer: Frequent sorting is required. Maintaining sorted order becomes costly with many changes.

Flashcard 64: For binary search, what is the typical return value for a successful search?

Answer: The index of the target element. Provides the location where the target was found.

Flashcard 65: State the time complexity of binary search in the worst case.

Answer: $O(\text{log } n)$. Eliminates half the search space with each comparison.

Flashcard 66: In binary search, if the target is greater than the middle element, what is the next step?

Answer: Search the right half of the dataset. Target must be in the larger half of the remaining elements.

Flashcard 67: Does binary search work on linked lists?

Answer: Not efficiently due to non-constant time access. Sequential access makes random indexing inefficient.

Flashcard 68: Does binary search require additional memory for its operations?

Answer: No, uses constant space $O(1)$. Only needs variables for indices, not extra arrays.

Flashcard 69: State the average time complexity of binary search.

Answer: $O(\text{log } n)$. Consistently eliminates half the search space each iteration.

Flashcard 70: Which algorithmic paradigm does binary search belong to?

Answer: Divide and conquer. Repeatedly divides the problem into smaller subproblems.

Flashcard 71: How does binary search determine the middle element of the dataset?

Answer: Middle index = $\frac{\text{low} + \text{high}}{2}$. Formula calculates the midpoint between current boundaries.

Flashcard 72: Identify the first step in performing a binary search.

Answer: Calculate the middle index of the dataset. Starting point to compare against the target value.

Flashcard 73: What is a common application of binary search in computer science?

Answer: Searching in databases. Efficiently locates records in sorted database indexes.

Flashcard 74: What is the space complexity of binary search?

Answer: $O(1)$. Only uses a few variables regardless of dataset size.

Flashcard 75: What is an iterative approach to implementing binary search?

Answer: Using a while loop to adjust 'low' and 'high'. Uses loops to repeatedly narrow the search boundaries.

Flashcard 76: What is the effect of binary search on a dataset with duplicate elements?

Answer: Finds one occurrence of the target. Standard behavior returns first match found, not all.

Flashcard 77: Identify the first step in performing a binary search.

Answer: Calculate the middle index of the dataset. Starting point to compare against the target value.

Flashcard 78: What is the primary requirement for applying binary search on a dataset?

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

Flashcard 79: Why is binary search not suitable for datasets with frequent updates?

Answer: Frequent sorting is required. Maintaining sorted order becomes costly with many changes.

Flashcard 80: In binary search, what happens if 'low' equals 'high'?

Answer: Check the element at 'low' or 'high'. Single element left to verify as target match.