Binary Search
What is searching, what is binary search, and why is it useful
Searching is an important operation used to find an element in a set of data. For example, every time a user completes an article on this website, we need to search our databases for the user to add points to their account. The most common form of this task is: Given an array of integers, what is the index of a given target element? For example, if we are given [1, 3, 5, 2, 4] and our target element is 5 we want to get its index, 2.
The simplest method to achieve this is linear search. Linear search works by iterating straight through an array and returning the index of the target element as soon as it finds it. Here’s what it would look like:
Code:
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
            
arr = [1, 3, 5, 2, 4]
print(linear_search(arr, 5))
print(linear_search(arr, 1))
print(linear_search(arr, 4))
Output:
> 2
> 0
> 4
Code:
class linearSearch {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 2, 4};
        System.out.println(linear_search(arr, 5));
        System.out.println(linear_search(arr, 1));
        System.out.println(linear_search(arr, 4));
    }
    static int linear_search(int[] arr, int target) {
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
Output:
> 2
> 0
> 4
Code:
#include <bits/stdc++.h>

using namespace std;

int linear_search(int arr[], int target) {
    for(int i = 0; i < 5; i++) {
        if(arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 2, 4};
    cout << linear_search(arr, 5) << "\n";
    cout << linear_search(arr, 1) << "\n";
    cout << linear_search(arr, 4);
    return 0;
}
Output:
> 2
> 0
> 4
In some cases, linear search is about as efficient as searching gets (e.g., in an array of random numbers). However, when your array is sorted, binary search is much faster.
Do you remember the last time you needed to find a word in a dictionary? If so, do you remember your strategy? If you simply flipped from left to right, it would take ages — especially if your word started with Z! However, if you started in the middle of the book, then flipped left or right depending on if the word you were looking for came after that page, repeating until you found the right word, you were emulating binary search, one of the most common, essential techniques in computer science.
Binary search is a super-efficient algorithm that finds a target element in sorted data (imagine how difficult it would be to find a word if your dictionary had words in random order!). Once your data is sorted, the algorithm works by continuously halving the possible locations of your element until you find it.
Binary search does this using a search window, or the window the algorithm is certain the target element is located in. This window is defined by a left and right index. Every iteration, the algorithm finds the center of the window (by averaging the left and right indices), compares the center to the target element, and figures out in which half of the window the target element is located. Then, it redefines the window to that half. Searching an integer array using binary search is implemented like this:
Code:
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    mid = (left + right) // 2 # this method of calculating mid is the most straightforward, but breaks in certain cases- google the better method!
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
            
    return -1
            
arr = [1, 4, 8, 9, 26]
print(binary_search(arr, 4))
print(binary_search(arr, 9))
print(binary_search(arr, 26))
Output:
> 1
> 3
> 4
Code:
class binarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 4, 8, 9, 26};
        System.out.println(binary_search(arr, 4));
        System.out.println(binary_search(arr, 9));
        System.out.println(binary_search(arr, 26));
    }
    static int binary_search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid = (left + right) / 2; // this method of calculating mid is the most straightforward, but breaks in certain cases- google the better method!
        
        while(left <= right) {
            mid = (left + right) / 2;
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
Output:
> 1
> 3
> 4
Code:
#include <bits/stdc++.h>

using namespace std;

int binary_search(int arr[], int target) {
    int left = 0;
    int right = 4;
    int mid = (left + right) / 2; // this method of calculating mid is the most straightforward, but breaks in certain cases- google the better method!
    
    while(left <= right) {
        mid = (left + right) / 2;
        if(arr[mid] == target) {
            return mid;
        } else if(arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 4, 8, 9, 26};
    cout << binary_search(arr, 4) << "\n";
    cout << binary_search(arr, 9) << "\n";
    cout << binary_search(arr, 26);
    return 0;
}
Output:
> 1
> 3
> 4
Common Mistake: Make sure your data is sorted!
Binary search is much faster than linear search. If the target element is the last element in the data, linear search will have a worst-case scenario of going through every single element before finding the correct one. This would take
N
operations to complete, where
N
is the size of the array. With binary search, the search window is cut in half every time the algorithm executes. This results in a much faster maximum of
log2(N)
operations.
However, that’s the maximum number of operations, not the actual number of operations. It’s important to know what data you are working with. For example, if your target element is always going to be the first element, linear search will always run faster than binary search on large arrays (1 operation is faster than
log2(N)
operations!). Know your data!
Binary search has a slew of useful applications in the real world. The most obvious is searching for a specific value (no kidding), but it is also applied in several more complicated algorithms as well. Its ability to cut down the time it takes to find a value helps dramatically in speeding up a program.
You can play with all the code we've used in this article on Replit:
Join our discord server for updates, announcements, future event planning, to ask questions, or just for fun!
Copyright ©2021 Howard County Hour of Code