Searching Algorithms

Searching Algorithms

Searching algorithms locate specific elements within data structures. Modern languages provide highly optimized built-in search methods that leverage appropriate data structures for optimal performance.

Think of finding a book: searching page-by-page is slow (linear search), but using an index or organized catalog enables instant retrieval (binary search, hash lookup).

Search Strategy Selection

graph TD
    A[Search Strategy] --> B{Data Sorted?}
    B -->|Yes| C[Binary Search - O log n]
    B -->|No| D{Need Fast Lookup?}

    D -->|Yes| E[Hash Table - O 1]
    D -->|No| F[Linear Search - O n]

    style C fill:#c8e6c9
    style E fill:#e3f2fd
    style F fill:#ffecb3

Time Complexity

Algorithm	Time	Space	Requirements
Hash Lookup	O(1) avg	O(n)	Hash table/set
Binary Search	O(log n)	O(1)	Sorted array
Linear Search	O(n)	O(1)	Any collection
BFS/DFS	O(V + E)	O(V)	Graph traversal

Hash-Based Search (Fastest)

Use hash tables/sets for O(1) average-case lookups when order doesn't matter.

JavaKotlinTypeScriptDartSwiftPython

import java.util.*;

// HashMap lookup - O(1)
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
boolean exists = map.containsKey("apple");  // O(1)
Integer value = map.get("apple");           // O(1) -> 5

// HashSet membership - O(1)
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
boolean found = set.contains("apple");      // O(1) -> true

// HashMap lookup - O(1)
val map = mutableMapOf<String, Int>()
map["apple"] = 5
map["banana"] = 3
val exists = map.containsKey("apple")       // O(1) -> true
val value = map["apple"]                    // O(1) -> 5

// HashSet membership - O(1)
val set = mutableSetOf<String>()
set.add("apple")
set.add("banana")
val found = set.contains("apple")           // O(1) -> true

// Map lookup - O(1)
const map = new Map<string, number>();
map.set("apple", 5);
map.set("banana", 3);
const exists = map.has("apple");            // O(1) -> true
const value = map.get("apple");             // O(1) -> 5

// Set membership - O(1)
const set = new Set<string>();
set.add("apple");
set.add("banana");
const found = set.has("apple");             // O(1) -> true

// Map lookup - O(1)
Map<String, int> map = {};
map["apple"] = 5;
map["banana"] = 3;
bool exists = map.containsKey("apple");     // O(1) -> true
int? value = map["apple"];                  // O(1) -> 5

// Set membership - O(1)
Set<String> set = {};
set.add("apple");
set.add("banana");
bool found = set.contains("apple");         // O(1) -> true

// Dictionary lookup - O(1)
var dict = [String: Int]()
dict["apple"] = 5
dict["banana"] = 3
let exists = dict.keys.contains("apple")    // O(1) -> true
let value = dict["apple"]                   // O(1) -> 5

// Set membership - O(1)
var set = Set<String>()
set.insert("apple")
set.insert("banana")
let found = set.contains("apple")           // O(1) -> true

# Dictionary lookup - O(1)
dict_map = {"apple": 5, "banana": 3}
exists = "apple" in dict_map                # O(1) -> True
value = dict_map.get("apple")               # O(1) -> 5

# Set membership - O(1)
set_data = {"apple", "banana"}
found = "apple" in set_data                 # O(1) -> True

Binary Search (Sorted Data)

Efficiently searches sorted arrays by repeatedly halving the search space. O(log n) time complexity.

JavaKotlinTypeScriptDartSwiftPython

import java.util.Arrays;

// Built-in binary search - O(log n)
int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};
int index = Arrays.binarySearch(sortedArray, 7);  // Returns 3

// Custom implementation
public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;  // Not found
}

// Built-in binary search - O(log n)
val sortedArray = intArrayOf(1, 3, 5, 7, 9, 11, 13, 15)
val index = sortedArray.binarySearch(7)               // Returns 3

// Custom implementation
fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}

// Custom binary search - O(log n)
function binarySearch(arr: number[], target: number): number {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
const index = binarySearch(sortedArray, 7);           // Returns 3

// Custom binary search - O(log n)
int binarySearch(List<int> arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) ~/ 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

List<int> sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
int index = binarySearch(sortedArray, 7);             // Returns 3

// Custom binary search - O(log n)
func binarySearch(_ arr: [Int], target: Int) -> Int {
    var left = 0, right = arr.count - 1
    while left <= right {
        let mid = left + (right - left) / 2
        if arr[mid] == target { return mid }
        if arr[mid] < target { left = mid + 1 }
        else { right = mid - 1 }
    }
    return -1
}

let sortedArray = [1, 3, 5, 7, 9, 11, 13, 15]
let index = binarySearch(sortedArray, target: 7)      // Returns 3

import bisect

# Built-in binary search - O(log n)
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15]
index = bisect.bisect_left(sorted_array, 7)           # Returns 3

# Custom implementation
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

index = binary_search(sorted_array, 7)                # Returns 3

Linear Search (Unsorted Data)

Checks each element sequentially. O(n) time complexity. Use when data is unsorted and small, or hash tables aren't available.

JavaKotlinTypeScriptDartSwiftPython

// Linear search - O(n)
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

// Using streams
int[] arr = {4, 2, 7, 1, 9};
boolean found = Arrays.stream(arr).anyMatch(x -> x == 7);  // true

// Linear search - O(n)
fun linearSearch(arr: IntArray, target: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return -1
}

// Using built-in methods
val arr = intArrayOf(4, 2, 7, 1, 9)
val found = arr.contains(7)                           // true
val index = arr.indexOf(7)                            // 2

// Linear search - O(n)
function linearSearch(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

// Using built-in methods
const arr = [4, 2, 7, 1, 9];
const found = arr.includes(7);                        // true
const index = arr.indexOf(7);                         // 2

// Linear search - O(n)
int linearSearch(List<int> arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

// Using built-in methods
List<int> arr = [4, 2, 7, 1, 9];
bool found = arr.contains(7);                         // true
int index = arr.indexOf(7);                           // 2

// Linear search - O(n)
func linearSearch(_ arr: [Int], target: Int) -> Int {
    for (i, val) in arr.enumerated() {
        if val == target { return i }
    }
    return -1
}

// Using built-in methods
let arr = [4, 2, 7, 1, 9]
let found = arr.contains(7)                           // true
let index = arr.firstIndex(of: 7)                     // 2

# Linear search - O(n)
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Using 'in' operator
arr = [4, 2, 7, 1, 9]
found = 7 in arr                                      # True
index = arr.index(7)                                  # 2

Graph Search (BFS/DFS)

For searching in graphs and trees. See Graphs section for detailed implementations.

• Breadth-First Search (BFS): Level-by-level exploration using a queue. Finds shortest path in unweighted graphs
• Depth-First Search (DFS): Deep exploration using recursion/stack. Good for pathfinding and cycle detection

Applications

• Fast Lookups: Use hash tables/sets for O(1) membership testing
• Sorted Data: Use binary search for O(log n) searches in sorted arrays
• Range Queries: Binary search to find boundaries in sorted data
• Graph Navigation: BFS for shortest paths, DFS for connectivity
• Database Indexing: B-trees combine aspects of binary search for disk-based storage

Search Algorithm Selection

Scenario	Algorithm	Reason
Frequent lookups, no order needed	Hash table	O(1) average case
Sorted array	Binary search	O(log n) efficient
Unsorted small dataset	Linear search	Simple, adequate
Graph/tree traversal	BFS/DFS	Natural fit
Range queries	Binary search	Find boundaries

Key Insight: Choose the data structure first (hash table, sorted array, graph), then use the appropriate built-in search method. Custom implementations rarely outperform well-tested standard libraries.