Searching Algorithms

Searching algorithms find specific elements in data structures. The efficiency varies dramatically based on data organization.

Linear Search

Linear search checks each element sequentially until finding the target or reaching the end.

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

Time Complexity: O(n)
Space Complexity: O(1)
Use Case: Unsorted arrays, small datasets

Binary Search

Binary search repeatedly divides a sorted array in half, eliminating half the search space each iteration.

Requirements: Array must be sorted

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  # Search right half
        else:
            right = mid - 1  #Search left half
    
    return -1

Time Complexity: O(log n)
Space Complexity: O(1)

Binary Search Variants

Find Insert Position

def search_insert(arr, target):
    """Find index where target should be inserted."""
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

Search in Rotated Sorted Array

def search_rotated(arr, target):
    """Search in rotated sorted array [4,5,6,7,0,1,2]."""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        
        # Left half is sorted
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

Search Space Reduction

Binary search principle works on any "search space" where you can eliminate half based on a condition.

Find Square Root

def sqrt(x):
    """Find integer square root using binary search."""
    if x < 2:
        return x
    
    left, right = 1, x // 2
    
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        
        if square == x:
            return mid
        elif square < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return right  # Largest integer whose square <= x

Comparison: Linear vs Binary Search

When to Use Binary Search

• Data is sorted
• Random access available (arrays, not linked lists)
• Large dataset (n > 100)
• Frequent searches

When to Use Linear Search

• Data is unsorted
• Small dataset
• Searching linked list
• One-time search

Quiz

Key Takeaways

✅ Linear search: O(n), works on any array
✅ Binary search: O(log n), requires sorted array
✅ Binary search is exponentially faster for large datasets
✅ Search space reduction principle applies beyond arrays
✅ Choose wisely based on data size and organization

Master both searching techniques for optimal problem-solving! 🚀