Algorithm	Worst Case	Average Case	Best Case	Space Complexity
Linear Search	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Binary Search	$O(log.n)$	$O(log.n)$	$O(1)$	$O(1)$
Jump Search	$O(\sqrt(n))$	$O(\sqrt(n))$	$O(1)$	$O(1)$

Linear Search

Linear search is a simple search algorithm used to find the presence of a target value within a list or array of elements. It sequentially checks each element of the list until either the target value is found or the end of the list is reached.

Pseudo Code

function linearSearch(list, target):
    for i from 0 to length(list) - 1 do
        if list[i] equals target then
            return true
        end if
    end for
    return false
end function

Complexity

Time Complexity

• Worst case: $O(n)$
• Average case: $O(n)$
• Best case: $O(1)$

Space Complexity

• Worst: $O(1)$

Pros and Cons

Pros

• Simplicity: Linear search is a straightforward algorithm to understand and implement
• Applicability: Linear search can be used on any list or array, regardless of whether it is sorted or unsorted. It works on both numeric and non-numeric data.
• Flexibility: Linear search can be easily modified to handle various search conditions. For example, it can be adapted to search for multiple occurrences of the target value or to stop after finding the first occurrence.

Cons

• Inefficiency: Slower search times for large lists
• Performance on Sorted Lists: If the list is sorted, linear search is less efficient compared to algorithms designed for sorted data, such as binary search
• Lack of Early Termination: Linear search does not terminate early after finding the target value. Even if the target is found early in the list, the algorithm continues searching until the end, resulting in unnecessary iterations
• Limited Scalability: Linear search becomes less practical for very large lists or datasets, as the time taken to search through each element increases proportionally

Usage

• Small Lists: Linear search is suitable for small lists or arrays where the number of elements is relatively low.
• Unsorted Lists: If the list is unsorted or lacks any specific order, linear search can be a practical choice. Linear search does not rely on any assumptions about the data order, making it applicable in situations where the data is randomly arranged.
• Simple Implementations: Linear search is straightforward to implement, making it useful in situations where simplicity is prioritized over search efficiency
• Partial Matches: Linear search can be modified to search for partial matches or specific patterns within the elements of a list. It can be helpful when searching for specific substrings or patterns in strings, or for finding elements with specific properties within a collection.
• Sequential Data Access: Linear search is effective when the data being searched is stored sequentially in memory or requires sequential access

Binary Search

Binary Search is a searching algorithm used to locate a target element in a sorted array efficiently. It follows a divide-and-conquer approach, repeatedly dividing the search range in half until the target element is found or determined to be absent.

The algorithm starts by comparing the target element with the middle element of the array. If they match, the search is successful. If the target is smaller, the search continues in the lower half of the array. If the target is larger, the search continues in the upper half. This process is repeated until the target is found or the search range is reduced to zero.

Pseudo Code

function binarySearch(list, target):
    low = 0
    high = length(list) - 1
    
    while low <= high do
        mid = (low + high) / 2
        
        if list[mid] equals target then
            return mid
        else if list[mid] < target then
            low = mid + 1
        else
            high = mid - 1
    
    return -1
end function

Complexity

Time Complexity

• Worst case: $O(log.n)$
• Average case: $O(log.n)$
• Best case: $O(1)$

Space Complexity

• Worst: $O(1)$

Pros and Cons

Pros

• Efficiency: Binary search offers significant efficiency gains over linear search for large and sorted lists. It reduces the search space by half at each step, resulting in a logarithmic time complexity.
• Applicability: Binary search works on sorted lists, making it suitable for scenarios where the data is known to be sorted beforehand
• Versatility: Binary search can be used for a wide range of applications, such as searching for a specific element, finding the first or last occurrence of an element, or determining if a value exists in a sorted list.

Cons

• Requirement of sorted data: Binary search requires the data to be sorted before applying the algorithm
• Limited to random access: Binary search performs well on data structures that allow efficient random access, such as arrays

Usage

• Sorted Lists: Binary search is most effective when the data is sorted in ascending or descending order. It relies on the property of sorted data to quickly narrow down the search space, making it an ideal choice for sorted lists or arrays
• Large Datasets: Binary search excels in scenarios where the dataset is large
• Static Data: Binary search is well-suited for static or unchanging datasets. Since it requires a sorted list, it is best applied when the data does not undergo frequent modifications or updates.
• Efficient Retrieval: When there is a need to retrieve specific elements from a sorted collection or find the position of a particular value, binary search provides an efficient solution.
• Performance Optimization: Binary search is often used to optimize search operations. For instance, it can be utilized to improve the performance of search algorithms in databases or when searching for specific items in large datasets.

Jump Search

Jump Search is a searching algorithm that works on sorted arrays. It is an improvement over linear search as it reduces the number of comparisons by jumping ahead a fixed number of steps instead of iterating through each element one by one.

The algorithm works by dividing the array into blocks of equal size and then performing a linear search in each block. If the target element is found in a block, the search is considered successful. Otherwise, it jumps to the next block and repeats the process until either the element is found or the end of the array is reached.

Pseudocode

procedure jumpSearch(array: sorted array, target: element)
    n = length of array
    step = √n  // Determine the jump size
    
    // Find the block where the element may exist
    prev = 0
    while array[min(step, n) - 1] < target do
        prev = step
        step = step + √n
        if prev >= n then
            return -1  // Element not found
    
    // Perform linear search in the found block
    while array[prev] < target do
        prev = prev + 1

        // If we reached next block or end of array, element is not present.
        if prev == min(step, n) then
            return -1  // Element not found
    
    // If the element is found
    if array[prev] == target then
        return prev
    
    return -1  // Element not found
end procedure

Complexity

Time Complexity

• Worst case: O(√n) - When the element is at the end of the array or not present in the array, it requires traversing through √n blocks, each with a linear search.
• Average case: O(√n)
• Best case: O(1) - When the target element is the first element of the array, no jumps or comparisons are required.

Space Complexity

• Worst: O(1) - The algorithm uses a constant amount of additional space for storing variables.

Pros and Cons

Pros

• Efficient for large sorted arrays, especially when the elements are uniformly distributed.
• Better than linear search, as it reduces the number of comparisons.

Cons

• Requires the array to be sorted beforehand.
• Not suitable for unsorted or dynamically changing arrays.

Use cases

• Searching for an element in a large sorted array, such as searching for a name in a phone directory.
• Finding a specific value in a sorted list of items, such as searching for a specific price in a price list.