Construct and trace algorithms to implement a linear search and a binary search for data retrieval

Linear Search

How it works: Sequentially checks each element from the start until the target is found or the list ends. Works on any list — sorted or unsorted.

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

Trace example:

arr  = [4, 2, 7, 1, 9, 3]
target = 7

i=0: arr[0]=4  → 4 != 7  → continue
i=1: arr[1]=2  → 2 != 7  → continue
i=2: arr[2]=7  → 7 == 7  → return 2  ✅

Complexity:

	Value
Best case	O(1) — target is the first element
Worst case	O(n) — target is last or not present
Average case	O(n)
Space	O(1)

---

Binary Search

How it works: Repeatedly halves a sorted list, comparing the target to the middle element to decide which half to continue searching. Requires a sorted list to work correctly.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1     # Target is in right half
        else:
            high = mid - 1    # Target is in left half

    return -1                  # Not found

Trace example:

arr   = [1, 3, 5, 7, 9, 11, 13]
target = 7

Step 1: low=0, high=6, mid=3
        arr[3]=7 → 7 == 7 → return 3  ✅

# Step-by-step with mid values:
arr   = [1, 3, 5, 7, 9, 11, 13]
               ↑
             mid=3 (value=7) → found!

# Recursive version
def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1

    mid = (low + high) // 2

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

Complexity:

	Value
Best case	O(1) — target is the middle element
Worst case	O(log n) — target is at an edge or absent
Average case	O(log n)
Space (iterative)	O(1)
Space (recursive)	O(log n) — call stack depth

---

Linear Search vs Binary Search

Property	Linear Search	Binary Search
Data requirement	Any list (sorted or not)	Must be sorted
Best case	O(1)	O(1)
Average case	O(n)	O(log n)
Worst case	O(n)	O(log n)
Space (iterative)	O(1)	O(1)
Implementation	Simple	Moderate