Linear and Binary Searching

Flashcards on Linear and Binary Searching Algorithms

Data storage and retrieval

Putting a data item in a store and retrieving a specific item.

Fast Storage (Slow Retrieval)

Appending the latest data to the end of the store, resulting in fast storage but slow retrieval.

Slow Storage (Fast Retrieval)

Maintaining data in sorted order, resulting in slow storage but fast retrieval using binary search.

Theoretical Time Complexity

The relationship between the size of the input and the algorithm's running time.

Big-O Notation

Captures the upper bound on the time required for an algorithm to run based on the input size.

Constant Time

O(1)

Logarithmic Time

O(log N)

Linear Time

O(N)

N log N Time

O(N log N)

Quadratic Time

O(N^2)

Cubic Time

O(N^3)

Exponential Time

O(2^N)

Linear Searching

Scanning through array elements to find the index of the first occurrence of an integer x in an unsorted array.

Complexity of Linear Search Algorithm

O(N)

Binary Search

An algorithm that can only be used on sorted arrays and has a better theoretical time complexity than linear searching.

Complexity of Binary Search Algorithm

O(log N)

Left Half of Array

Consists of A[0..M-1] in a binary search.

Right Half of Array

Consists of A[M+1..N-1] in a binary search.

Binary search method

Divide and conquer