Introduction to Binary Search with Practical Examples

Picture yourself searching for a word in a massive dictionary. Instead of flipping through every page randomly, You start by selecting a midpoint in the dictionary and check if the word appears on that page. If you find it, your search ends there. However, if the word isn’t on that page, you narrow down your search to either the previous or next half of the dictionary.

Continuing this process, you progressively divide the dictionary into smaller segments, each time focusing on the segment where the word might be located. Eventually, you pinpoint the exact page where the word resides. This systematic approach mirrors the efficiency of binary search, enabling you to swiftly locate the word without scanning every page.

Binary Search

Binary search is a searching algorithm used to find the position of a target value within a sorted array or list. It follows a divide-and-conquer approach, systematically reducing the search space in each iteration by half. This algorithm is particularly efficient for large datasets as it eliminates half of the remaining elements with each step, resulting in a logarithmic time complexity.

Binary search is applicable to any monotonic characteristic search space, enabling the search for elements that meet specific monotonic conditions within the space. This is because binary search relies on the inherent monotonicity of the search space, simplifying the efficient location of the desired elements within it.

Sufficient Conditions for Binary Search

  • Monotonicity: The search space must exhibit monotonicity, meaning that the value of elements either consistently increases or consistently decreases as we traverse the data structure. This monotonicity ensures that binary search can reliably determine which half of the search space to explore next.
  • Random Access: Binary search requires the ability to access elements in the data structure in constant time. This is typically achieved through random access, which allows accessing any element in the data structure directly without needing to traverse through the entire structure.

Working Principle of Binary Search

Binary Search algorithm works in few steps,

  1. Divide the Search Space:

    • Find the middle index “mid” to divide the search space into two halves.

  2. Compare with Middle Element:

    • Compare the middle element of the search space with the key.
    • If the key is found at the middle element, the process is terminated.

  3. Choose Next Search Space:

    • If the key is not found at the middle element, determine which half will be used as the next search space.
    • If the key is smaller than the middle element, use the left side for the next search.
    • If the key is larger than the middle element, use the right side for the next search.

  4. Continuation of the Process:

    • Repeat steps 1-3 until either:
    • The key is found, and the search is successful.
    • The total search space is exhausted, indicating that the key is not present.

Example: Finding a Key in a Sorted Array

Let’s explore how binary search works by using it to find a key in a sorted array.

Satisfies Sufficient Conditions ?

  1. Monotonicity: Monotonicity refers to the consistent pattern of elements in the array. In a sorted array, elements are arranged either in non-decreasing or non-increasing order. For example, in a non-decreasing sorted array, each element is greater than or equal to the preceding element.

  2. Random Access: Random access implies the ability to directly access any element in the array in constant time. In a sorted array, this means we can quickly access the middle element using its index without needing to traverse the array sequentially.

So, with the sorted array satisfying these conditions, binary search becomes applicable.

Binary Search Walkthrough

Sure, let’s walk through the steps of binary search to find the key 5 in the sorted array [1, 3, 5, 6, 7, 12, 19].

  1. Initialization:

    • Initially, the search space encompasses the entire array.
    • Set left pointer to index 0 and right pointer to index 6.
    • Calculate the midpoint
    • The middle element of the array is 6.

  2. Comparison:

    • Compare the key 5 with the middle element 6: Since 5 < 6, we discard the right half of the search space and focus on the left half.
Sorted Array

  1. Adjustment of Pointers:
    • Update the right pointer to mid - 1.
    • The search space now includes only the elements [1, 3, 5].
Sorted Array
  1. Repeat Steps 1-3:
    • Step 1: Calculate the new midpoint
    • The middle element of the remaining search space is 3.
Sorted Array

  • Step 2: Compare the key 5 with the middle element 3: Since 5 > 3, discard the left half of the search space.
  • Step 3: Update the left pointer to mid + 1. - The search space now includes only the element 5.
Sorted Array

  1. Final Comparison:

    • The only remaining element in the search space is 5.
    • Compare the key 5 with the middle element 5: The key matches the middle element, indicating that the search is successful.

  2. Conclusion:

    • The key 5 is found at index 2 in the array [1, 3, 5, 6, 7, 12, 19].

Implementation in C

#include <stdio.h>

// Function to perform binary search
int binarySearch(int arr[], int n, int key) {
    int left = 0;
    int right = n - 1;

    // Iterate until left pointer is less than or equal to right pointer
    while (left <= right) {
        // Calculate the midpoint
        int mid = left + (right - left) / 2;

        // If key is found at the midpoint, return the index
        if (arr[mid] == key) {
            return mid;
        }
        // If key is greater than the element at midpoint, search in the right half
        else if (arr[mid] < key) {
            left = mid + 1;
        }
        // If key is smaller than the element at midpoint, search in the left half
        else {
            right = mid - 1;
        }
    }

    // If key is not found, return -1
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 6, 7, 12, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 5;

    // Perform binary search
    int index = binarySearch(arr, n, key);

    // Print the result
    if (index != -1) {
        printf("Key %d found at index %d\n", key, index);
    } else {
        printf("Key %d not found\n", key);
    }

    return 0;
}
Output:
Key 5 found at index 2

Time Complexity of Binary Search

The time complexity of binary search is O(log n), where n is the number of elements in the array. In each iteration of binary search, the search space is divided in half, effectively halving the number of elements to search through. This logarithmic behavior is due to the fact that the search space is reduced exponentially with each iteration.

Application of Binary Search

  1. Debugging Linear Code: Imagine you’re fixing errors in a long sequence of code. Instead of checking each line randomly, binary search helps you identify where the mistake might be. You start by testing the middle section of the code. If it works fine, you know the issue lies after that point. Otherwise, you backtrack to the previous midpoint to search for the bug. This process continues, dividing the code into smaller parts until you find the exact location of the error. This method efficiently isolates bugs, much like how binary search quickly finds a target value in a sorted list.

  2. Searching in Databases: When searching for specific records in a database, binary search speeds up the process. Imagine a massive library catalog. Instead of checking each book randomly, binary search helps you narrow down your search. You start by looking at the middle section of the catalog. If the book you’re looking for is alphabetically after that point, you focus on the second half. Otherwise, you explore the first half. This systematic approach reduces search time, especially when the database is sorted by indexed fields.

  3. File Systems: In a computer’s file system, binary search assists in locating files or directories efficiently. Think of a cluttered filing cabinet. Instead of rummaging through every drawer, binary search helps you navigate the directory tree. You start by checking the midpoint. If the file you’re searching for is alphabetically after that point, you explore the right side. Otherwise, you focus on the left side. This method is particularly useful in large file systems where finding specific files quickly is essential.

  4. Finding Words in Dictionaries: When searching for a word in a dictionary, binary search expedites the process. Imagine a thick dictionary with thousands of words. Instead of flipping through each page randomly, binary search helps you locate the word efficiently. You start by opening the dictionary in the middle. If the word you’re looking for comes later alphabetically, you turn to the latter half. Otherwise, you check the first half. This systematic approach allows for quick access to definitions or translations, especially since dictionaries are often arranged in alphabetical order.

  5. Mathematical Calculations: Binary search aids in various mathematical applications, improving computational efficiency. For instance, when finding roots of equations or locating elements in sorted lists, binary search streamlines the process. Imagine solving a complex equation. Instead of guessing randomly, binary search helps you narrow down the possible solutions. You start by testing the midpoint of the solution range. If the result is too high, you focus on the lower half, and vice versa. This method optimizes mathematical calculations, making them faster and more accurate.

Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online

Previous
Introduction to Tree Data Structure with Practical Examples
Next
Sliding Window Technique with Two Practical Examples