Skip to content

Searching Algorithms Overview

This section contains documentation for searching algorithms that locate specific elements within data structures.

Available Searching Algorithms

  • Basic Linear Search: Sequential search through unsorted data
  • Linear Search All: Find all occurrences of a target value
  • Conditional Search: Search based on custom predicates
  • Backwards Search: Search from end to beginning
  • Sentinel Search: Optimized linear search with sentinel technique
  • Standard Binary Search: Efficient search in sorted arrays
  • Recursive Binary Search: Recursive implementation
  • Leftmost/Rightmost Search: Find first/last occurrence in duplicates
  • Range Search: Find all occurrences range
  • Insert Position: Find where to insert while maintaining sort order
  • Conditional Binary Search: Search with custom conditions
  • Closest Element: Find element closest to target value
  • 2D Matrix Search: Search in row/column sorted matrices

Algorithm Characteristics

Algorithm Time Complexity Space Complexity Requirements
Linear Search O(n) O(1) None
Binary Search O(log n) O(1) iterative, O(log n) recursive Sorted array

When to Use Each Algorithm

Use Linear Search When:

  • Array is unsorted
  • Small datasets (< 100 elements typically)
  • Need to find all occurrences
  • Memory access pattern matters more than comparisons
  • Searching with complex conditions

Use Binary Search When:

  • Array is sorted or can be sorted
  • Large datasets
  • Frequent searches on same dataset
  • Memory is not a constraint
  • Need optimal search performance

Performance Considerations

Linear Search

  • Best Case: O(1) - target is first element
  • Worst Case: O(n) - target is last element or not present
  • Average Case: O(n/2) - target is in middle on average

Binary Search

  • Best Case: O(1) - target is middle element
  • Worst Case: O(log n) - consistent performance
  • Average Case: O(log n) - consistent performance

Common Usage Patterns

from algo.algorithms.searching import linear_search, binary_search

# Linear search - works on any array
unsorted_data = [3, 1, 4, 1, 5, 9, 2, 6]
index = linear_search(unsorted_data, 5)  # Returns 4

# Binary search - requires sorted array
sorted_data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index = binary_search(sorted_data, 5)  # Returns 4

Finding All Occurrences

from algo.algorithms.searching import linear_search_all, binary_search_range

# Linear search for all occurrences
data = [1, 2, 3, 2, 4, 2, 5]
all_indices = linear_search_all(data, 2)  # Returns [1, 3, 5]

# Binary search for range of occurrences
sorted_data = [1, 2, 2, 2, 3, 4, 5]
start, end = binary_search_range(sorted_data, 2)  # Returns (1, 3)

Conditional Searching

from algo.algorithms.searching import linear_search_with_condition, binary_search_with_condition

# Find first element greater than threshold
data = [1, 3, 5, 7, 9, 11]
index = linear_search_with_condition(data, lambda x: x > 6)  # Returns 3 (value 7)

# Binary search with condition (on sorted data)
index = binary_search_with_condition(data, lambda x: x > 6)  # Returns 3 (value 7)

Error Handling

All searching algorithms handle common edge cases:

# Empty arrays
linear_search([], 5)  # Returns -1
binary_search([], 5)  # Returns -1

# Single element arrays
linear_search([42], 42)  # Returns 0
linear_search([42], 5)   # Returns -1

# Target not found
linear_search([1, 2, 3], 4)  # Returns -1
binary_search([1, 2, 3], 4)  # Returns -1

Integration Examples

With Different Data Types

# String searching
names = ['Alice', 'Bob', 'Charlie', 'David']
index = linear_search(names, 'Charlie')  # Returns 2

# Sorted string searching
sorted_names = ['Alice', 'Bob', 'Charlie', 'David']
index = binary_search(sorted_names, 'Charlie')  # Returns 2

# Custom object searching
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __eq__(self, other):
        return self.age == other.age

    def __lt__(self, other):
        return self.age < other.age

people = [Person('Alice', 25), Person('Bob', 30), Person('Charlie', 35)]
target = Person('Someone', 30)
index = linear_search(people, target)  # Finds Bob

Performance Optimization

# For frequent searches on same data, sorting once pays off
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# If searching multiple times, sort once
sorted_data = sorted(data)

# Then use binary search for better performance
for target in [1, 3, 5, 7, 9]:
    index = binary_search(sorted_data, target)