Description: Introduction to searching algorithms. In this session, we will cover the basics of looking for a certain target in a data structure: array, List, etc. In this session, we will talk about sequential or linear binary search, its implementation and also its complexity.
ACM CCECC
N/A
AP CS A
[The Sequential Search Algorithm]
CON-2.K Apply sequential/linear search algorithms to search for specific information in an array or ArrayList objects.
CON-2.K.1 There are standard algorithms for searching.
CON-2.K.2 Sequential/linear search algorithms check each element in order until the desired value is found or all elements in the array or ArrayList have been checked.
CS2
N/A
Description: In this session, we analyze one of the most powerful searching algorithms: binary search. As we did with linear search, we will cover the fundamentals of the search, its implementation, and its complexity to understand how it compares in speed to its linear counterpart.
Code:
ACM CCECC
N/A
AP CS A
[The Binary Search]
CON-2.P.1 Data must be in sorted order to use the binary search algorithm.
CON-2.P.2 The binary search algorithm starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each iteration until the desired value is found or all elements have been eliminated.
CON-2.P.4 The binary search algorithm can be written either iteratively or recursively.
CS2
[Search Algorithms]
AL-08. Implement common search algorithms, including linear and binary searches.
Description: After having analyzed both searching techniques, it is time to go deeper into the comparisons between linear and binary search. For that, we will be calculating the Big-Oh of both algorithms and demonstrating the results by code.
Code:
ACM CCECC
[Analysis of Algorithms]
AL-02. Estimate time and space complexities for a given algorithm using Big-O notation.
AL-05. Apply an appropriate algorithmic approach to a given problem.
AP CS A
[Analysis of Algorithms]
CON-2.P.3 Binary search can be more efficient than sequential/linear search. EXCLUSION STATEMENT(EK CON-2.P.3)—Search algorithms other than sequential/linear and binary search are outside the scope of the course and AP Exam
CS2
[Search Algorithms]
130.422.c.4.g Design, construct, evaluate, and compare search algorithms, including linear searching and binary searching;
[Analysis of Algorithms]
130.422.c.4.j Compare and contrast search and sort algorithms, including linear, quadratic, and recursive strategies, for time/space efficiency;