Module 1: Searching and Big O Part B

Linear Search

Linear search is a simple search algorithm that checks each element in a list sequentially until the desired element is found. It's straightforward but can be inefficient for large data sets.

When using linear search:

• We check each element one by one
• Works on both sorted and unsorted data
• Time complexity is O(n) - linear time
• Best for small lists or when data is not sorted

public static int linearSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i; // Found the target, return its index
        }
    }
    return -1; // Target not found
}

Binary Search

Binary search is an efficient algorithm that works on sorted arrays by repeatedly dividing the search interval in half. It has a logarithmic time complexity, making it much faster than linear search for large datasets.

When using binary search:

• The data must be sorted
• We repeatedly divide the search space in half
• Time complexity is O(log n) - logarithmic time
• Each step eliminates half of the remaining elements
• Only effective when data is sorted and indexed (like ArrayList)

public static int binarySearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // Check if target is at mid
        if (sortedArray[mid] == target) {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (sortedArray[mid] < target) {
            left = mid + 1;
        }
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    
    // Target not found
    return -1;
}

Binary Search on LinkedList

While binary search is highly efficient for ArrayList (with O(log n) time complexity), it performs poorly on LinkedList due to the lack of random access. In a LinkedList, each element access requires traversal from the beginning or end of the list, resulting in O(n) time complexity for access operations.

For LinkedLists, linear search is often more appropriate despite its theoretical inefficiency because the overhead of element access in binary search negates its advantages.

Big O Analysis

Big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Common Time Complexities:

• O(1) - Constant time: Operations that take the same amount of time regardless of input size
• O(log n) - Logarithmic time: Algorithms that divide the problem in half each time (like binary search)
• O(n) - Linear time: Operations that process each input element once (like linear search)
• O(n log n) - Linearithmic time: Algorithms like efficient sorting methods (merge sort, quicksort)
• O(n²) - Quadratic time: Operations with nested loops processing all elements (selection sort, bubble sort)

Algorithm Comparison:

• Linear Search: O(n) - has to potentially check all elements
• Binary Search on ArrayList: O(log n) - divides problem in half each iteration
• Binary Search on LinkedList: O(n) - random access is O(n), negating benefits
• Selection Sort: O(n²) - requires nested loops to compare and swap elements
• Merge Sort: O(n log n) - divides problem and merges results