DSA — Linear Search & Binary Search

Linear search checks each element until found — O(n) time, works on unsorted data.

Linear Search

Linear search checks each element until found — O(n) time, works on unsorted data.

Simple and fine for small lists.

Real-life example: Finding socks in an messy drawer — check one item at a time left to right.

Linear search

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

print(linear_search([4, 2, 7, 1], 7))

Binary Search

Binary search needs sorted data — halve the search space each step — O(log n).

Classic interview algorithm; implement with left/right pointers.

Real-life example: Finding a word in a dictionary — open middle, go left or right, repeat.

Binary search

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

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