What is linear search?
Linear search checks elements one at a time until it finds the target or reaches the end. It does not require sorted data.
Study 08. Searching Algorithms with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
What is linear search?
Linear search checks elements one at a time until it finds the target or reaches the end. It does not require sorted data.
What is binary search?
Binary search repeatedly compares the target with the middle element and discards the half where the target cannot occur.
Does linear search require sorted data?
No. Linear search works whether or not the collection is sorted.
What ordering requirement does binary search have?
Yes. Binary search requires the data to be sorted according to the same ordering used for comparisons.
What are linear search’s best- and worst-case times?
Linear search has best-case time O(1), when the first element matches, and worst-case time O(n), when the target is last or absent.
What are binary search’s best- and worst-case times?
With efficient indexed access, binary search has best-case time O(1) and worst-case time O(log n).
What invariant does binary search maintain?
Before each binary-search step, if the target exists, it must lie between low and high. Updates remove impossible positions while preserving that possibility.
How does binary search handle target < middle value?
For an ascending list, if the target is smaller than the middle value, set high to middle - 1 and search the lower half.
How does binary search handle target > middle value?
For an ascending list, if the target is larger than the middle value, set low to middle + 1 and search the upper half.
Why use low + (high - low) // 2 for the midpoint?
The expression low + (high - low) // 2 can avoid integer overflow that may occur with (low + high) // 2 when index values are very large.
How can binary search find the first or last duplicate?
Ordinary binary search may return any matching occurrence. To find the first, record a match and continue in the lower half; to find the last, continue in the upper half.
Which boundary cases should binary search handle?
A robust binary search must handle an empty list, targets outside the data range, matches at either boundary, and absent targets.
A practical review of the integrated Java skills, debugging habits, algorithm reasoning, and free-response strategies needed for AP Computer Science A.
A progressive guide to designing, operating, and testing systems that continue useful service despite component faults, overload, data loss, and recovery challenges.
A medium-difficulty quiz on how independently operated networks, protocols, addresses, naming systems, transport services, and routing mechanisms work together to form the Internet.
Learn how to create, modify, traverse, and analyze Java lists with ArrayList, wrapper types, standard algorithms, and the Collections utility class for AP Computer Science A.
Build a clear understanding of Java Boolean expressions, logical operators, selection statements, nested branching, equivalent logic, and systematic code tracing for AP Computer Science A.
A practical introduction to Java program structure, data types, operators, input and output, problem-solving strategy, testing, and debugging for AP Computer Science A.
A practical guide to Java inheritance, constructor chaining, method overriding, polymorphism, access control, and object behavior for tracing and writing AP Computer Science A programs.
A focused guide to Java classes, object references, constructors, methods, strings, wrapper classes, and API usage for AP Computer Science A.
A focused guide to Java primitive types, expression evaluation, numeric conversion, floating-point behavior, integer overflow, and common methods in the Math class for AP Computer Science A.
A focused review of Java primitive types, expression evaluation, numeric conversion, arithmetic behavior, Math methods, randomness, and tracing techniques for AP Computer Science A.
A progressive guide to how packet-switched networks encapsulate data, move it across links, and manage delay, throughput, queues, and congestion.
A structured guide to designing parallel and distributed systems through decomposition, communication, coordination, state management, scalability, and fault tolerance.