Searching Algorithms in Python

What Searching Tries to Answer

• Does the element exist?
• Where is it located?
• How fast can we find it?

---

Factors Affecting Search Performance

• Input size (n)
• Data structure used
• Whether the data is sorted
• Time and memory constraints

---

Linear search checks elements one by one until the target is found or the list ends.

---

When to Use Linear Search

• Data is unsorted
• Input size is small
• Simplicity matters more than speed

---

Python Implementation

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

print(linear_search([5, 3, 7, 1], 7))  # 2
print(linear_search([5, 3, 7, 1], 9))  # -1

---

Complexity

• Time:
  • Worst/Average: O(n)
  • Best case: O(1) (first element matches)
• Space: O(1)

---

Common Mistake

Returning only True/False when the problem explicitly asks for the index.

---

Binary search works only on sorted data. It repeatedly divides the search space into halves.

---

Why Binary Search Is Powerful

• Instead of checking n elements, it takes log₂(n) steps
• Example:
  • 1,000,000 elements → ~20 comparisons

---

Requirements

• Data must be sorted
• You must define what “match” means (any, first, or last occurrence)

---

Binary Search (Iterative)

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

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

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

    return -1

print(binary_search([1, 3, 5, 7, 9], 7))  # 3

---

Complexity

• Time: O(log n)
• Space: O(1) (iterative version)

---

Many interview problems rely on binary search variations, not the basic version.

---

First Occurrence (Lower Bound)

Find the first index where arr[index] == target.

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

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            ans = mid
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return ans

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

---

Last Occurrence (Upper Bound)

Find the last index where arr[index] == target.

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

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            ans = mid
            left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return ans

print(last_occurrence([1, 2, 2, 2, 3], 2))  # 3

---

Common Binary Search Mistakes

• Infinite loop due to incorrect boundary updates
• Using left < right instead of left <= right
• Incorrect mid update logic
• Forgetting sorted-data requirement

---

Tree searching depends on traversal strategy and tree structure.

---

Searching in a Binary Search Tree (BST)

BSTs allow efficient searching due to ordering.

def search_bst(root, target):
    if root is None:
        return False
    if root.data == target:
        return True
    if target < root.data:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)

---

Complexity

• Average: O(log n) (balanced BST)
• Worst: O(n) (skewed BST)

---

Graphs are searched using traversal algorithms.

---

BFS Search (Shortest Path in Unweighted Graphs)

from collections import deque

def bfs_search(graph, start, target):
    visited = set([start])
    q = deque([start])

    while q:
        node = q.popleft()
        if node == target:
            return True
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)
    return False

---

DFS Search

def dfs_search(graph, start, target, visited=None):
    if visited is None:
        visited = set()

    if start == target:
        return True

    visited.add(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            if dfs_search(graph, neighbor, target, visited):
                return True
    return False

---

Complexity (BFS / DFS)

• Time: O(V + E)
• Space: O(V) (visited + queue/stack)

---

Searching algorithms depend heavily on data structure and ordering:

• Linear Search: Simple, works on unsorted data, but slow
• Binary Search: Extremely fast but requires sorted input
• Binary Search Variants: First/last occurrence are interview favorites
• Trees: BST search is efficient when balanced
• Graphs: BFS and DFS are fundamental traversal-based searches