Searching Algorithms - Learn Step by Step

🤔 Why Should You Care About Searching Algorithms?

📱 Your Phone's Contact List

When you type a name, your phone uses binary search on the alphabetically sorted contacts to find matches instantly - even with thousands of contacts!

🔍 Google Search

Google uses sophisticated searching algorithms to find relevant pages from billions of websites in milliseconds. It's not just one search - it's multiple parallel searches!

📚 Dictionary Lookup

Finding a word in a dictionary uses binary search - you open to the middle, check if your word comes before or after, then repeat with the appropriate half!

🎮 Game Leaderboards

Finding your rank among millions of players uses efficient searching to quickly locate your score in a sorted database!

🛒 E-commerce Product Search

Amazon searches through millions of products using indexed searching algorithms to show you results in real-time as you type!

✈️ Flight Booking

Airlines use searching algorithms to find available seats, check prices, and match your preferences from thousands of flight combinations!

🏥 Medical Records

Hospitals use indexed searching to instantly retrieve patient records from databases containing millions of entries!

🎵 Music Recognition

Shazam uses searching algorithms to match audio fingerprints against a database of millions of songs in seconds!

📸 Face Recognition

Your phone uses searching algorithms to match faces in photos against stored facial data to organize your photo library!

💳 Credit Card Fraud Detection

Banks search through transaction patterns in real-time to identify suspicious activities among millions of transactions!

🌟 Level 1: The Basics (Start Here!)

Level 1

🔍 Linear Search - The Simple Detective

Imagine looking for your keys by checking every spot in your house, one by one. That's linear search!

🎮 Try Linear Search!

Enter numbers and search for a value. Watch how we check each element!

Linear Search in Python 🐍

def linear_search(arr, target):
    # Check each element one by one
    for i in range(len(arr)):
        # Found it! Return the index
        if arr[i] == target:
            return i
    
    # Not found after checking everything
    return -1

# Example: Finding a friend in a list
friends = ["Alice", "Bob", "Charlie", "David"]
position = linear_search(friends, "Charlie")
print(f"Found at index: {position}")  # Found at index: 2

Level 1

⚡ Binary Search - The Smart Detective

Like finding a page in a book - open to the middle, then go left or right based on the page number!

0 📘 1

1 📗 3

2 📙 5

3 (mid) 📕 7 👆

4 📓 9

5 📔 11

6 📒 13

Important: Binary search ONLY works on sorted arrays!

Binary Search - Divide and Conquer! 🎯

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        # Find the middle element
        mid = (left + right) // 2
        
        # Found it!
        if arr[mid] == target:
            return mid
        
        # Target is in the right half
        elif arr[mid] < target:
            left = mid + 1
        
        # Target is in the left half
        else:
            right = mid - 1
    
    return -1  # Not found

# Example: Finding a page number
pages = [1, 5, 10, 15, 20, 25, 30]
page_index = binary_search(pages, 15)
print(f"Page 15 is at index: {page_index}")  # Page 15 is at index: 3

🎨 Level 2: Common Patterns

Level 2

🎯 Two Pointers Pattern

Use two pointers moving towards each other to find pairs or check conditions!

1

Start: One pointer at beginning, one at end

2

Move: Based on the sum/condition

3

Meet: Stop when pointers cross

Two Sum in Sorted Array

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Need larger sum
        else:
            right -= 1  # Need smaller sum
    
    return []  # No pair found

Level 2

🔄 Modified Binary Search

Binary search variations for special cases!

Find First/Last Occurrence

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid  # Store result
            right = mid - 1  # Keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

⚠️ Common Mistake: Binary Search on Unsorted Array

# ❌ WRONG - Array is not sorted!
arr = [5, 2, 8, 1, 9]
result = binary_search(arr, 8)  # Will give wrong result!

✅ The Right Way

# ✅ CORRECT - Sort first or use linear search
arr = [5, 2, 8, 1, 9]
arr.sort()  # Now: [1, 2, 5, 8, 9]
result = binary_search(arr, 8)  # Works correctly!

💪 Practice Problems

Problem 1: Search in Rotated Array 🔄

Find an element in a sorted array that has been rotated (e.g., [4,5,6,7,0,1,2])

Think About It First! 🤔

How can you use binary search when the array is rotated?

Show Solution

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        
        # Check which half is sorted
        if arr[left] <= arr[mid]:
            # Left half is sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half is sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

Problem 2: Find Peak Element 🏔️

Find a peak element where arr[i] > arr[i-1] and arr[i] > arr[i+1]

Show Solution

def find_peak(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        # Compare with next element
        if arr[mid] < arr[mid + 1]:
            # Peak is in right half
            left = mid + 1
        else:
            # Peak is in left half (including mid)
            right = mid
    
    return left  # left == right is the peak

Problem 3: Search in 2D Matrix 📊

Search for a value in a sorted 2D matrix efficiently

Show Solution

def search_matrix(matrix, target):
    if not matrix:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    
    # Start from top-right corner
    row, col = 0, cols - 1
    
    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1  # Move left
        else:
            row += 1  # Move down
    
    return False

🚀 Level 3: Advanced Techniques

Level 3

🎯 Exponential Search

Useful for unbounded or infinite arrays!

Exponential Search - Jump and Binary!

def exponential_search(arr, target):
    # If target is at first position
    if arr[0] == target:
        return 0
    
    # Find range for binary search
    i = 1
    while i < len(arr) and arr[i] <= target:
        i *= 2
    
    # Binary search in the found range
    left = i // 2
    right = min(i, len(arr) - 1)
    
    return binary_search_range(arr, target, left, right)

Level 3

🔺 Ternary Search

Divide the array into three parts instead of two!

Ternary Search - Three-way Split

def ternary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        # Divide into three parts
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3
        
        if arr[mid1] == target:
            return mid1
        if arr[mid2] == target:
            return mid2
        
        if target < arr[mid1]:
            right = mid1 - 1
        elif target > arr[mid2]:
            left = mid2 + 1
        else:
            left = mid1 + 1
            right = mid2 - 1
    
    return -1

Level 3

🏃 Jump Search

Jump ahead by fixed steps, then do linear search!

Jump Search - Hop and Search

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))  # Optimal jump size
    prev = 0
    
    # Jump to find the block
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    
    # Linear search in the block
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    
    if arr[prev] == target:
        return prev
    
    return -1

📖 Quick Reference

Algorithm	Time Complexity	Space	When to Use	Requirements
Linear Search 🔍	O(n)	O(1)	📚 Small arrays, unsorted data	None
Binary Search ⚡	O(log n)	O(1)	🎯 Large sorted arrays	Sorted array
Jump Search 🏃	O(√n)	O(1)	📦 Large sorted arrays, between linear and binary	Sorted array
Exponential Search 📈	O(log n)	O(1)	♾️ Unbounded/infinite arrays	Sorted array
Ternary Search 🔺	O(log₃ n)	O(1)	📊 Unimodal functions	Sorted array
Interpolation Search 📍	O(log log n)	O(1)	📈 Uniformly distributed data	Sorted, uniform

Time Complexity in Plain English

🎯 Quick Decision Guide

Array not sorted? → Use Linear Search
Array sorted & small (< 100)? → Linear might be fine
Array sorted & large? → Binary Search
Don't know array size? → Exponential Search
Data uniformly distributed? → Interpolation Search
Need to find range? → Modified Binary Search
Multiple searches? → Consider sorting first

❌ Common Pitfalls

Using binary search on unsorted array
Integer overflow in mid calculation - Use: mid = left + (right - left) // 2
Off-by-one errors - Check <= vs < in loop condition
Not handling duplicates - Modify to find first/last
Forgetting edge cases - Empty array, single element