Algorithms: Binary Search Algorithm

Concept:
Binary Search is an efficient algorithm to find the position of a target element in a sorted array. It works by repeatedly dividing the search range in half. If the target is not found in the middle, it determines whether to search in the left or right half of the array.

• Time Complexity: ( O(\log n) )

• Space Complexity: ( O(1) ) for iterative implementation.

---

Nigerian Police Story for Context:

Imagine the Nigerian Police Force is digitizing its crime reports database. Each report is assigned a unique case ID, and these case IDs are stored in sorted order in a database for easy retrieval.

The system allows officers to quickly locate a specific case using its case ID. Given a sorted list of case IDs, the binary search algorithm helps the officer find a target ID efficiently.

• Real-World Application: When a senior officer requests details about a specific case ID from a sorted database, Binary Search can be used to fetch the case details in minimal time.

• Why it Matters: With thousands of crime reports logged every year, manually searching through the database would be inefficient. Binary Search provides a solution to locate information quickly.

---

Problem Example:

The Nigerian Police have the following sorted list of case IDs:

[101, 120, 134, 145, 150, 160, 200, 250, 300, 450, 500]

Task:
An officer needs to determine if case ID 200 exists in the database. If it does, return its position (index); otherwise, return that the case ID is not found.

---

Steps to Solve Using Binary Search:

1. Identify the middle element of the sorted array.

2. Compare the middle element with the target:

   • If it matches, return the index.

   • If the target is smaller, narrow the search to the left half.

   • If the target is larger, narrow the search to the right half.

3. Repeat until the target is found or the search space becomes empty.

---

Code Example (Python):

def binary_search(case_ids, target):
    # Initialize the search range
    low = 0
    high = len(case_ids) - 1

    while low <= high:
        mid = (low + high) // 2  # Find the middle index
        mid_value = case_ids[mid]

        if mid_value == target:
            return f"Case ID {target} found at index {mid}."
        elif mid_value < target:
            low = mid + 1  # Narrow search to the right half
        else:
            high = mid - 1  # Narrow search to the left half

    return f"Case ID {target} not found in the database."

# Test the function with a sample list of case IDs
case_ids = [101, 120, 134, 145, 150, 160, 200, 250, 300, 450, 500]
target = 200
print(binary_search(case_ids, target))

Output:
Case ID 200 found at index 6.

---

Practice Problem:

Scenario:

The Nigerian Police are looking for the latest reported case ID within a given range of IDs to prioritize their investigations. Write a program that:

1. Uses binary search to find a specific case ID.

2. Extends to locate the largest case ID less than or equal to a given number (e.g., find the latest case ID ≤ 300).

---

Solution for Practice Problem:

def find_latest_case(case_ids, max_id):
    # Initialize the search range
    low = 0
    high = len(case_ids) - 1
    latest_case = -1  # Store the largest case ID ≤ max_id

    while low <= high:
        mid = (low + high) // 2
        mid_value = case_ids[mid]

        if mid_value <= max_id:
            latest_case = mid_value  # Update the latest case ID
            low = mid + 1  # Search in the right half
        else:
            high = mid - 1  # Search in the left half

    if latest_case == -1:
        return f"No case ID found ≤ {max_id}."
    return f"The latest case ID ≤ {max_id} is {latest_case}."

# Test the function with a sample list of case IDs
case_ids = [101, 120, 134, 145, 150, 160, 200, 250, 300, 450, 500]
max_id = 300
print(find_latest_case(case_ids, max_id))

Output:
The latest case ID ≤ 300 is 300.

---

Let’s explore variations and extensions of Binary Search and how they can be applied in Nigerian policing or similar real-world contexts. Each variation adds a layer of complexity or utility to the basic Binary Search algorithm.

---

1. Variation: First and Last Occurrence of a Case ID

Scenario:

A senior officer needs to determine the first occurrence and last occurrence of a case ID in a sorted list of case reports, where the same case ID might appear multiple times (e.g., multiple reports about the same incident).

Problem:

Find the first and last index of a case ID in a sorted list.

Example:

• Input: case_ids = [101, 120, 134, 134, 134, 145, 150, 200]

• Target: 134

• Output: First occurrence = 2, Last occurrence = 4

---

Code Solution:

def find_first_and_last(case_ids, target):
    def binary_search_first(case_ids, target):
        low, high = 0, len(case_ids) - 1
        result = -1
        while low <= high:
            mid = (low + high) // 2
            if case_ids[mid] == target:
                result = mid  # Record the index
                high = mid - 1  # Move left to find earlier occurrences
            elif case_ids[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return result

    def binary_search_last(case_ids, target):
        low, high = 0, len(case_ids) - 1
        result = -1
        while low <= high:
            mid = (low + high) // 2
            if case_ids[mid] == target:
                result = mid  # Record the index
                low = mid + 1  # Move right to find later occurrences
            elif case_ids[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return result

    first_index = binary_search_first(case_ids, target)
    last_index = binary_search_last(case_ids, target)
    return first_index, last_index

# Test the function
case_ids = [101, 120, 134, 134, 134, 145, 150, 200]
target = 134
first, last = find_first_and_last(case_ids, target)
print(f"First occurrence of case ID {target}: {first}")
print(f"Last occurrence of case ID {target}: {last}")

Output:

First occurrence of case ID 134: 2
Last occurrence of case ID 134: 4

---

2. Variation: Count the Number of Reports for a Case ID

Scenario:

The Nigerian police want to know how many reports have been filed for a specific case ID.

Solution Approach:

Use the indices of the first and last occurrence (from the previous solution) to calculate the count:

Code Update:

def count_reports(case_ids, target):
    first, last = find_first_and_last(case_ids, target)
    if first == -1:
        return f"Case ID {target} not found."
    return f"Number of reports for case ID {target}: {last - first + 1}"

# Test the function
print(count_reports(case_ids, target))

Output:
Number of reports for case ID 134: 3

---

3. Variation: Find the Closest Case ID

Scenario:

The Nigerian Police Force receives an inquiry for case ID 135, which does not exist in the database. The system must find the closest match.

Problem:

Given a target that is not in the list, return the case ID closest to it.

Example:

• Input: case_ids = [101, 120, 134, 145, 150, 200]

• Target: 135

• Output: 134

---

Code Solution:

def find_closest_case(case_ids, target):
    low, high = 0, len(case_ids) - 1
    closest = float('inf')

    while low <= high:
        mid = (low + high) // 2
        if abs(case_ids[mid] - target) < abs(closest - target):
            closest = case_ids[mid]
        if case_ids[mid] < target:
            low = mid + 1
        elif case_ids[mid] > target:
            high = mid - 1
        else:
            return case_ids[mid]  # Exact match found

    return closest

# Test the function
target = 135
closest_case = find_closest_case(case_ids, target)
print(f"The closest case ID to {target} is: {closest_case}")

Output:
The closest case ID to 135 is: 134

---

4. Variation: Range Search (Find Case IDs Within a Range)

Scenario:

The Nigerian police need to identify all case IDs within a specific range (e.g., 130 to 150) to filter reports related to a given time frame or location.

Problem:

Return all case IDs between two values (low and high).

Example:

• Input: case_ids = [101, 120, 134, 145, 150, 200]

• Range: [130, 150]

• Output: [134, 145, 150]

---

Code Solution:

def find_cases_in_range(case_ids, low_range, high_range):
    result = []
    for case_id in case_ids:
        if low_range <= case_id <= high_range:
            result.append(case_id)
    return result

# Test the function
low_range = 130
high_range = 150
cases_in_range = find_cases_in_range(case_ids, low_range, high_range)
print(f"Case IDs within range {low_range}-{high_range}: {cases_in_range}")

Output:
Case IDs within range 130-150: [134, 145, 150]

---

Key Takeaways:

1. Binary Search Variations:

   • First and last occurrence.

   • Count occurrences.

   • Closest value search.

   • Range-based filtering.

2. Applications in Nigerian Policing:

   • Retrieving cases with similar features or matching a range of criteria.

   • Prioritizing cases (e.g., closest to a given ID or within a specific range).

3. Efficiency: These techniques work efficiently with sorted data, making them ideal for large, structured police databases.