DSA Searching

Searching is one of the most fundamental operations in computing. Given a collection of data, searching means finding whether a specific element exists and, if so, where it is located. The efficiency of a search algorithm depends significantly on whether the data is sorted or unsorted.

This topic covers the two most essential searching algorithms: Linear Search and Binary Search, along with their practical implementations in Python.

Linear Search

Linear search checks every element in a list one by one, from start to finish, until the target element is found or the list is exhausted. It works on both sorted and unsorted data.

How Linear Search Works

1. Start at the first element.
2. Compare it with the target.
3. If they match, return the index.
4. If not, move to the next element.
5. Repeat until found or the list ends.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i        # Found — return index
    return -1               # Not found

books = ["Harry Potter", "Dune", "1984", "Moby Dick", "Hamlet"]
result = linear_search(books, "1984")
print("Found at index:", result)   # Output: Found at index: 2

result = linear_search(books, "Sherlock")
print("Found at index:", result)   # Output: Found at index: -1

Linear Search — Time Complexity

• Best case: O(1) — target is the first element.
• Average case: O(n/2) → simplified to O(n).
• Worst case: O(n) — target is the last element or not present.

When to Use Linear Search

• Data is unsorted and not sortable.
• The list is very small.
• Only a single search is needed on the data.

Binary Search

Binary search is a significantly faster algorithm that works only on sorted data. It repeatedly cuts the search space in half by comparing the target with the middle element.

The Key Idea

Imagine looking up a word in a dictionary. Instead of reading from page 1, open the dictionary to the middle. If the target word comes before the middle, search the left half. If it comes after, search the right half. Each step eliminates half of the remaining pages.

How Binary Search Works (Step-by-Step)

1. Set two pointers: left = 0, right = last index.
2. Calculate the middle: mid = (left + right) // 2.
3. If arr[mid] == target, return mid.
4. If target > arr[mid], move left = mid + 1 (search right half).
5. If target < arr[mid], move right = mid - 1 (search left half).
6. Repeat until left > right (target not found).

Iterative Binary Search

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid                  # Found
        elif arr[mid] < target:
            left = mid + 1              # Search right half
        else:
            right = mid - 1             # Search left half

    return -1                           # Not found

sorted_numbers = [5, 12, 18, 23, 35, 47, 61, 78, 90]
print(binary_search(sorted_numbers, 47))   # Output: 5
print(binary_search(sorted_numbers, 99))   # Output: -1

Recursive Binary Search

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1   # Base case — not found

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

numbers = [3, 9, 15, 21, 33, 45, 60]
print(binary_search_recursive(numbers, 33, 0, len(numbers) - 1))   # Output: 4

Binary Search — Time Complexity

• Best case: O(1) — target is the middle element.
• Average case: O(log n)
• Worst case: O(log n)

For a list of 1 million elements, binary search requires at most about 20 comparisons. Linear search might require up to 1,000,000.

Comparing Linear and Binary Search

Side by Side on 1,000,000 Elements

• Linear Search: Up to 1,000,000 comparisons.
• Binary Search: At most 20 comparisons (log₂ 1,000,000 ≈ 20).

Requirement

• Linear Search: Works on any data (sorted or unsorted).
• Binary Search: Requires sorted data.

Practical Application: Search in a Real Problem

Finding a Student's Rank

def find_rank(scores, target_score):
    scores_sorted = sorted(scores)
    return binary_search(scores_sorted, target_score)

student_scores = [72, 88, 91, 65, 78, 95, 83, 70]
sorted_scores = sorted(student_scores)
print("Sorted scores:", sorted_scores)

idx = binary_search(sorted_scores, 88)
print(f"Score 88 is at sorted position {idx}")
# Output: Score 88 is at sorted position 5

Searching in Python with the bisect Module

Python's standard library includes the bisect module for binary search on sorted lists.

import bisect

sorted_list = [10, 20, 30, 40, 50, 60]

# Find insertion point (also tells if element exists)
idx = bisect.bisect_left(sorted_list, 40)
if idx < len(sorted_list) and sorted_list[idx] == 40:
    print(f"Found 40 at index {idx}")   # Output: Found 40 at index 3
else:
    print("Not found")

Key Points

• Linear search checks every element — O(n) time — works on any data.
• Binary search repeatedly halves the search space — O(log n) time — requires sorted data.
• Binary search is dramatically faster for large datasets: 20 steps vs 1,000,000 for a million elements.
• Binary search can be implemented iteratively or recursively; iterative is preferred to avoid stack overhead.
• Python's bisect module provides a built-in, optimized binary search implementation.
• Choosing the right search algorithm depends on whether the data is sorted and how often the search is performed.