Searching Algorithms - AP Computer Science A

How does binary search determine which half of the array to search next?

Compares the middle element with the target. Comparison result determines which half to eliminate.
What is an advantage of linear search?

Simplicity and no need for sorted data. Works with any data arrangement without preprocessing.
Which searching algorithm divides the dataset in half at each step?

Binary search. Uses divide-and-conquer strategy to eliminate half the search space.
How does binary search achieve efficiency compared to linear search?

By reducing the search space exponentially. Halves search space each step versus linear progression.
State the time complexity of binary search in the average case.

$O(\text{log}\text{ }n)$ . Binary search halves the search space at each step.
Identify a situation that would lead to linear search outperforming binary search.

A very small dataset or unsorted data. Linear search avoids sorting overhead for small datasets.
Which searching algorithm is more efficient for small datasets?

Linear search. Simple implementation with low overhead for small arrays.
What condition triggers the best-case scenario for binary search?

The target is the middle element. Found immediately without additional comparisons needed.
Identify the searching algorithm with $O(n)$ complexity for both average and worst case.

Linear search. Sequential search has consistent linear time complexity.
How does linear search find an element in an array?

Checks each element sequentially. Examines elements one by one from beginning to end.
What is the main advantage of binary search over linear search?

Faster search time on sorted arrays. Logarithmic complexity significantly outperforms linear complexity.
Identify the main disadvantage of linear search.

Inefficient for large datasets; time complexity is $O(n)$ . Must check every element sequentially in worst case.
What type of algorithm is a binary search classified as?

Divide and conquer algorithm. Systematically divides problem into smaller subproblems.
What is the first step in a binary search algorithm?

Identify the middle element of the array. Start with the midpoint to divide search space.
State a scenario where linear search is more suitable than binary search.

When the data is unsorted. Binary search requires sorted data as prerequisite.
What kind of search is typically used when data is consistently changing?

Linear search, due to lack of sorting requirement. Dynamic data makes maintaining sorted order impractical.
Which algorithm can be easily adapted to work with linked lists?

Linear search. Sequential traversal is natural for linked data structures.
State the condition under which binary search may not function correctly.

When the array is unsorted. Binary search requires ordered data to function properly.
What is the primary purpose of a searching algorithm?

To find a specific value within a data structure. Searching algorithms locate elements within collections of data.
What is the worst-case time complexity of binary search?

$O(\text{log}\text{ }n)$ . Maximum comparisons needed is $\text{log}_2\text{ }n$ .
What data structure is essential for efficient binary search?

Sorted array or list. Binary search needs random access for efficient indexing.
What prerequisite must be met for binary search to function correctly?

The array must be sorted. Binary search requires ordered data to eliminate half the possibilities.
What is the main criterion for choosing between linear and binary search?

Whether the data is sorted or not. Data organization determines which algorithm is applicable.
Name a searching algorithm that works on unsorted data.

Linear search. Sequential search doesn't require data to be pre-sorted.
Which search technique is inherently sequential?

Linear search. Examines elements one after another in order.
Which search algorithm requires direct access to elements for efficiency?

Binary search. Random access enables efficient middle element selection.
What is the time complexity of linear search in the worst case?

$O(n)$ . Must examine every element when target is last or absent.
Which algorithm is preferred for searching a large, sorted list?

Binary search. Logarithmic time complexity is much faster than linear.
For binary search, what is the initial step before performing the algorithm?

Sort the array. Binary search only works on pre-sorted collections.
What is the space complexity of binary search?

$O(1)$ for iterative, $O(\text{log}\text{ }n)$ for recursive. Iterative uses constant space; recursive uses call stack.
What is a limitation of using binary search on linked lists?

Inefficient due to no direct access to middle elements. Linked lists lack direct indexing for middle element access.
How does binary search reduce the problem size at each step?

By half. Eliminates half the remaining elements each iteration.
Which searching algorithm has a time complexity of $O(1)$ in the best case?

Hash table search. Hash tables provide constant-time lookup with proper hash function.
Which searching algorithm is optimal for searching linked lists?

Linear search. No random access to middle elements in linked structures.
What is the key operation performed in each step of binary search?

Comparison with the middle element. Middle element comparison guides next search direction.
State the best-case time complexity for linear search.

$O(1)$ . Target element is found at the first position checked.
What are the two main types of searching algorithms?

Linear search and binary search. These are the fundamental search techniques in computer science.
Which search method is easier to implement for various data structures?

Linear search. Simple sequential approach works universally.
Which algorithm is preferable for dynamic data structures where frequent insertions occur?

Linear search. No need to maintain sorted order during insertions.
State the primary characteristic of data suitable for binary search.

Data must be sorted. Ordering enables efficient divide-and-conquer approach.

Study these flashcards