Module 3: Searching

Master the fundamentals of searching algorithms. Learn how to implement and analyze searching algorithms.

Module Objectives

Upon completion of this module you will be able to:

Implement a linear search algorithm and understand its O(n) time complexity
Implement a binary search algorithm and understand its O(log n) time complexity
Compare the efficiency of linear and binary search algorithms
Identify when to use each search algorithm based on data characteristics
Apply search algorithms to solve real-world programming problems

Linear Search

Understanding Linear Search

Linear search is the simplest search algorithm. It sequentially checks each element in a collection until the target is found or the collection is exhausted.

        # Linear search implementation
        def linear_search(arr, target):
        for i, value in enumerate(arr):
        if value == target:
        return i # Return the index where target is found
        return -1 # Return -1 if target is not found

        # Example usage
        numbers = [10, 24, 56, 7, 89, 42, 13]
        print(linear_search(numbers, 89)) # 4
        print(linear_search(numbers, 100)) # -1
      

Time Complexity:

Best Case: O(1) - Element found at the first position
Average Case: O(n) - Element found after checking half the elements
Worst Case: O(n) - Element found at the last position or not found

Space Complexity: O(1) - Uses a constant amount of extra space

Advantages of Linear Search:

Simple to implement
Works on both sorted and unsorted arrays
No pre-processing required
Efficient for small datasets

Disadvantages:

Inefficient for large datasets (O(n) time complexity)
Does not take advantage of sorted data

Optimized Linear Search

We can optimize linear search by adding early termination conditions or implementing search strategies like the sentinel search:

        # Linear search with sentinel
        def sentinel_linear_search(arr, target):
        n = len(arr)
        last = arr[-1]
        arr[-1] = target
        i = 0
        while arr[i] != target:
        i += 1
        arr[-1] = last
        if i < n - 1 or last==target: return i return -1 

Binary Search

Understanding Binary Search

Binary search is a divide-and-conquer algorithm that efficiently finds a target value in a sorted array. It repeatedly divides the search space in half, eliminating half of the remaining elements at each step.

          # Binary search implementation (iterative)
          def binary_search(arr, target):
          left = 0
          right = len(arr) - 1
          while left <= right: mid=left + (right - left) // 2 if arr[mid]==target: return mid if arr[mid] < target:
            left=mid + 1 else: right=mid - 1 return -1 # Example usage sorted_numbers=[2, 5, 8, 12, 16, 23, 38, 56, 72,
            91] print(binary_search(sorted_numbers, 23)) # 5 print(binary_search(sorted_numbers, 25)) # -1 

Recursive Binary Search

Binary search can also be implemented recursively:

              # Binary search implementation (recursive)
              def binary_search_recursive(arr, target, left=0, right=None):
              if right is None:
              right = len(arr) - 1
              # Base case: element not found
              if left > right:
              return -1
              # Calculate middle index
              mid = left + (right - left) // 2
              # Check if target is at mid
              if arr[mid] == target:
              return mid
              # Recursive cases
              if arr[mid] < target: # Search right half return binary_search_recursive(arr, target, mid + 1, right)
                else: # Search left half return binary_search_recursive(arr, target, left, mid - 1) 

Time Complexity:

Best Case: O(1) - Element found at the middle position
Average Case: O(log n) - Logarithmic time complexity
Worst Case: O(log n) - Element not found or at the edge

Space Complexity:

Iterative: O(1) - Constant extra space
Recursive: O(log n) - Call stack space proportional to recursion depth

Advantages of Binary Search:

Very efficient for large datasets - O(log n) is much faster than O(n) for large n
Requires fewer comparisons than linear search

Disadvantages:

Requires sorted data
Sorting may offset the advantage if data is initially unsorted
Not suitable for linked lists (requires random access)

Comparison: Linear vs. Binary Search

Aspect	Linear Search	Binary Search
Time Complexity	O(n)	O(log n)
Data Requirement	Works on sorted or unsorted data	Requires sorted data
Best For	Small datasets, unsorted data	Large datasets, sorted data
Implementation	Simple	More complex
Data Structure	Works with arrays and linked lists	Requires random access (arrays)

Practical Example: Searching in a phonebook

Linear Search: Start with the first page and check each page one by one
Binary Search: Open to the middle, decide whether to go left or right, repeat

For a phonebook with 1000 pages:

Linear search: up to 1000 checks
Binary search: at most 10 checks (log₂ 1000 ≈ 10)

Practice with LeetCode Problems

Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are an excellent alternative for practicing search algorithms.

Linear Search Problems:

Find Numbers with Even Number of Digits - Apply linear search with filtering
Richest Customer Wealth - Linear search with nested arrays
Check If N and Its Double Exist - Search problem that can be solved with linear search

Binary Search Problems:

Binary Search - Basic implementation of binary search
Search Insert Position - Find position to insert into a sorted array
First Bad Version - Application of binary search
Find First and Last Position of Element in Sorted Array - More advanced binary search problem