Binary Search

Time Complexity

Best	Average	Worst
Ω(1)	O(log n)	O(log n)

Space Complexity

Worst
O(1)

Overview

We already have good context on algorithms from the sorting ones and from the introduction to Searching algorithms in the previous section, so let's go straight to the point here.

Binary search is an algorithm that is used to find a value in a list quickly. The 'tradeoff' is that the list needs to be presorted as the concept cannot be applied on random data.

So imagine (or actually, don't - simply look at the animation!) you have a sorted list of numbers like [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], and you want to find the number 9.

Here's how binary search works step-by-step:

Preparation: Before starting the search, make sure the list is sorted in ascending order.

Initialization: You start by looking at the middle element of the list, which is 5 in this case. Since 9 is greater than 5, you know that 9 must be in the right half of the list.

Searching Process: Now, you focus on the right half of the list, which is [6, 7, 8, 9, 10]. The middle element of this sublist is 8. Since 9 is greater than 8, you narrow your search to the right again.

Searching Process (again): Now, you're left with the sublist [9, 10]. The middle element of this sublist is 9, which matches the target value you're looking for! You've found it!

Termination: Binary search terminates successfully, and it returns the index of the target value, which is 8 (remember that array indexing starts from 0).

In this example, binary search was able to find the number 9 in just two steps, even though there are ten elements in the list. This shows how efficient binary search can be, especially for large datasets which results in O(log n) time complexity.

Of course, these key advantages make Binary Search a great choice for many scenarios like searching in databases, cryptography, famous version control (Git?), searching in Trees (the famous Binary Search Tree, for instance) and others.

Code

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Target not found
 
# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 9
index = binary_search(arr, target)
if index != -1:
    print(f"Found {target} at index {index}.")
else:
    print(f"{target} is not found in the array.")

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
 
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Target not found
}
 
// Example usage:
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 9;
const index = binarySearch(arr, target);
if (index !== -1) {
    console.log(`Found ${target} at index ${index}.`);
} else {
    console.log(`${target} is not found in the array.`);
}

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // Target not found
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 9;
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("Found " + target + " at index " + index + ".");
        } else {
            System.out.println(target + " is not found in the array.");
        }
    }
}

#include <stdio.h>
 
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
 
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Target not found
}
 
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int index = binarySearch(arr, size, target);
    if (index != -1) {
        printf("Found %d at index %d.\n", target, index);
    } else {
        printf("%d is not found in the array.\n", target);
    }
    return 0;
}

<?php
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
 
    while ($left <= $right) {
        $mid = $left + floor(($right - $left) / 2);
        if ($arr[$mid] == $target) {
            return $mid;
        } else if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1; // Target not found
}
 
// Example usage:
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
$target = 9;
$index = binarySearch($arr, $target);
if ($index != -1) {
    echo "Found $target at index $index.\n";
} else {
    echo "$target is not found in the array.\n";
}
?>

We always try to improve this course so if you spot errors, inconsistencies or other issues, contact us.

Linear Search Quiz