🔍 Search Algorithms in Computer Science

🔍 Search Algorithms in Computer Science#

🧠 What Is a Search Algorithm?#

A search algorithm is a method for finding a specific item or value within a data structure such as an array, list, tree, or graph. It answers the question:

“Where is the item I’m looking for?”

Search algorithms are fundamental to computing, powering everything from database queries to AI pathfinding.

📂 Types of Search Algorithms#

1. Linear Search#

Description: Scans each element in a list sequentially until the target is found.
Best Case: O(1) (target is first element)
Worst Case: O(n) (target is last or not present)
Use Case: Small or unsorted datasets.

2. Binary Search#

Description: Repeatedly divides a sorted list in half to locate the target.
Best Case: O(1)
Average/Worst Case: O(log n)
Use Case: Large, sorted datasets.

3. Hash-Based Search#

Description: Uses a hash function to map keys to indices for constant-time lookup.
Time Complexity: O(1) average, O(n) worst (due to collisions)
Use Case: Dictionaries, sets, symbol tables.

4. Tree-Based Search (e.g., BST Search)#

Description: Traverses a binary search tree to find a value.
Time Complexity: O(log n) average, O(n) worst (unbalanced tree)
Use Case: Hierarchical or dynamically updated data.

5. Graph Search (DFS/BFS)#

Description: Explores nodes in a graph using depth-first or breadth-first strategies.
Time Complexity: O(V + E)
Use Case: Pathfinding, network traversal, AI.

🔄 Searching vs Sorting#

Feature	Searching	Sorting
Goal	Find a specific item	Arrange items in a specific order
Input Requirement	May require sorted data (e.g., binary search)	Works on unsorted data
Output	Index or presence of item	Entire dataset reordered
Examples	Linear, Binary, Hash Search	Bubble, Merge, Quick Sort

🧠 Conceptual Questions#

Why does binary search require sorted data?
How does hashing achieve constant-time search?
What trade-offs exist between tree-based and hash-based search?
When would you prefer BFS over DFS in graph search?
How does the structure of data affect search performance?

📝 Mini Quiz#

Question 1:
Which search algorithm is most efficient for large sorted arrays?

A) Linear Search
B) Binary Search
C) Hash Search
D) DFS
✅ Correct Answer: B

Question 2:
Which search algorithm uses a hash function to locate items?

A) Binary Search
B) Tree Search
C) Hash Search
D) BFS
✅ Correct Answer: C

Question 3:
Which search algorithm explores all neighbors before going deeper?

A) DFS
B) BFS
C) Binary Search
D) Hash Search
✅ Correct Answer: B

🎉 Fun Facts About Searching#

🧠 Binary search is so efficient it can search a billion items in ~30 steps.
🧩 Hash tables are the backbone of Python’s dict and set types.
🕸️ Graph search algorithms are used in Google Maps, social networks, and AI.
🧪 Search algorithms are often combined with sorting for optimal performance (e.g., sort first, then binary search).

🔍 Reflection Prompt#

Think of a real-world scenario (e.g., searching a contact, finding a route, locating a file).
Which search algorithm would be most appropriate and why? Consider data structure, speed, and memory usage.

import numpy as np
import ipywidgets as widgets
from IPython.display import display, Markdown

### 🔍 Search Algorithms
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def binary_search(arr, target):
    arr = sorted(arr)
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def hash_search(arr, target):
    lookup = {val: i for i, val in enumerate(arr)}
    return lookup.get(target, -1)

# 🧠 Algorithm dictionary
algorithms = {
    "Linear Search": linear_search,
    "Binary Search": binary_search,
    "Hash Search": hash_search
}

### 🎛️ Widgets
size_slider = widgets.IntSlider(value=20, min=10, max=100, step=10, description="Data Size:")
target_input = widgets.IntText(value=42, description="Target Value:")
algo_dropdown = widgets.Dropdown(options=list(algorithms.keys()), value="Linear Search", description="Algorithm:")
run_button = widgets.Button(description="Run Search", button_style='success')
output = widgets.Output()

### 🧪 Run search
def on_run_click(b):
    output.clear_output()
    np.random.seed(0)
    data = np.random.randint(0, 100, size_slider.value).tolist()
    target = target_input.value
    algo_name = algo_dropdown.value
    func = algorithms[algo_name]
    result = func(data, target)
    with output:
        display(Markdown(f"### 🔍 {algo_name} Result"))
        print(f"Data: {data}")
        print(f"Target: {target}")
        if result != -1:
            print(f"✅ Found at index {result}")
        else:
            print("❌ Not found")

run_button.on_click(on_run_click)

### 🚀 Display UI
display(size_slider, target_input, algo_dropdown, run_button, output)

import numpy as np
import time
import matplotlib.pyplot as plt
import ipywidgets as widgets
from IPython.display import display, Markdown

# 🔍 Search Algorithms
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def binary_search(arr, target):
    arr = sorted(arr)
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def hash_search(arr, target):
    lookup = {val: i for i, val in enumerate(arr)}
    return lookup.get(target, -1)

# 🧠 Algorithm dictionary
algorithms = {
    "Linear Search": linear_search,
    "Binary Search": binary_search,
    "Hash Search": hash_search
}

# 🎛️ Widgets
size_slider = widgets.IntSlider(value=1000, min=100, max=10000, step=100, description="Data Size:")
target_input = widgets.IntText(value=42, description="Target Value:")
compare_button = widgets.Button(description="Compare Performance", button_style='info')
output = widgets.Output()

# 📊 Compare performance
def on_compare_click(b):
    output.clear_output()
    np.random.seed(0)
    data = np.random.randint(0, 10000, size_slider.value).tolist()
    target = target_input.value
    times = {}
    results = {}

    for name, func in algorithms.items():
        start = time.time()
        index = func(data, target)
        duration = time.time() - start
        times[name] = duration
        results[name] = index

    with output:
        display(Markdown("### 📊 Search Algorithm Performance Summary"))
        print(f"🔢 Data Sample (first 20 of {len(data)}): {data[:20]}")
        print(f"🎯 Target Value: {target}\n")
        for name in algorithms:
            found_msg = f"✅ Found at index {results[name]}" if results[name] != -1 else "❌ Not found"
            print(f"{name:<15} ➤ Time: {times[name]:.6f} sec | {found_msg}")

        # Plotting
        plt.figure(figsize=(8, 5))
        plt.bar(times.keys(), times.values(), color='lightgreen')
        plt.ylabel("Execution Time (seconds)")
        plt.title("Search Algorithm Comparison")
        plt.grid(True, linestyle='--', alpha=0.5)
        plt.tight_layout()
        plt.show()

compare_button.on_click(on_compare_click)

# 🚀 Display UI
display(size_slider, target_input, compare_button, output)