Binary Search
Intuition
Binary search is an efficient array search algorithm. It works by narrowing down the search range by half each time. If you have looked up a word in a physical dictionary, you've already used binary search in real life. Let's look at a simple example:
Given a sorted array of integers and an integer called target, find the element that equals the target and return its index. If the element is not found, return -1.
The key observation here is that the array is sorted. We pick a random element in the array and compare it to the target.
- If we happen to pick the element that equals the target (how lucky!), then bingo. We don't need to do any more work; we return its index.
- If the element is smaller than the target, then we know the target cannot be found in the section to the left of the current element, since everything to the left is even smaller. So, we discard the current element and everything on the left from the search range.
- If the element is larger than the target, then we know the target cannot be found in the section to the right of the current element, since everything to the right is even larger. So, we discard the current element and everything on the right from the search range.
We repeat this process until we find the target. Instead of picking a random element, we always pick the middle element in the current search range. This way, we can discard half of the options and shrink the search range by half each time. This gives us O(log(N)) runtime.
This idea can be implemented both iteratively and recursively. However, the major difference is that the iterative version of binary search uses O(1) memory while the recursive version uses O(log(N)) memory.
Try it yourself
Implementation
The search range is represented by the left and right indices that start from both ends of the array and move towards each other as we search. When moving the index, we discard elements and shrink the search range.
Time Complexity: O(log(n))
1def binary_search(arr: list[int], target: int) -> int:
2 left, right = 0, len(arr) - 1
3 # <= because left and right could point to the same element, < would miss it
4 while left <= right:
5 # double slash for integer division in python 3,
6 # we don't have to worry about integer `left + right` overflow
7 # since python integers can be arbitrarily large
8 mid = (left + right) // 2
9 # found target, return its index
10 if arr[mid] == target:
11 return mid
12 # middle less than target, discard left half by making left search boundary `mid + 1`
13 if arr[mid] < target:
14 left = mid + 1
15 # middle greater than target, discard right half by making right search boundary `mid - 1`
16 else:
17 right = mid - 1
18 return -1 # if we get here we didn't hit above return so we didn't find target
19
20if __name__ == "__main__":
21 arr = [int(x) for x in input().split()]
22 target = int(input())
23 res = binary_search(arr, target)
24 print(res)
251import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int binarySearch(List<Integer> arr, int target) {
8 int left = 0;
9 int right = arr.size() - 1;
10
11 while (left <= right) { // <= here because left and right could point to the same element, < would miss it
12 int mid = left + (right - left) / 2; // use `(right - left) / 2` to prevent `left + right` potential overflow
13 // found target, return its index
14 if (arr.get(mid) == target) return mid;
15 if (arr.get(mid) < target) {
16 // middle less than target, discard left half by making left search boundary `mid + 1`
17 left = mid + 1;
18 } else {
19 // middle greater than target, discard right half by making right search boundary `mid - 1`
20 right = mid - 1;
21 }
22 }
23 return -1; // if we get here we didn't hit above return so we didn't find target
24 }
25
26 public static List<String> splitWords(String s) {
27 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
28 }
29
30 public static void main(String[] args) {
31 Scanner scanner = new Scanner(System.in);
32 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
33 int target = Integer.parseInt(scanner.nextLine());
34 scanner.close();
35 int res = binarySearch(arr, target);
36 System.out.println(res);
37 }
38}
391using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static int BinarySearch(List<int> arr, int target)
8 {
9 int left = 0;
10 int right = arr.Count - 1;
11 while (left <= right) // <= here because left and right could point to the same element, < would miss it
12 {
13 int mid = left + (right - left) / 2; // use `(right - left) / 2` to prevent `left + right` potential overflow
14 // found target, return its index
15 if (arr[mid] == target) return mid;
16 if (arr[mid] < target)
17 {
18 // middle less than target, discard left half by making left search boundary `mid + 1`
19 left = mid + 1;
20 }
21 else
22 {
23 // middle greater than target, discard right half by making right search boundary `mid - 1`
24 right = mid - 1;
25 }
26 }
27 return -1; // if we get here we didn't hit above return so we didn't find target
28 }
29
30 public static List<string> SplitWords(string s)
31 {
32 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
33 }
34
35 public static void Main()
36 {
37 List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
38 int target = int.Parse(Console.ReadLine());
39 int res = BinarySearch(arr, target);
40 Console.WriteLine(res);
41 }
42}
431"use strict";
2
3function binarySearch(arr, target) {
4 let left = 0;
5 let right = arr.length - 1;
6
7 // <= because left and right could point to the same element, < would miss it
8 while (left <= right) {
9 const mid = left + Math.floor((right - left) / 2); // use `(right - left) / 2` to prevent `left + right` potential overflow
10 if (arr[mid] === target) return mid; // found target, return its index
11 if (arr[mid] < target) {
12 // middle less than target, discard left half by making left search boundary `mid + 1`
13 left = mid + 1;
14 } else {
15 // middle greater than target, discard right half by making right search boundary `mid - 1`
16 right = mid - 1;
17 }
18 }
19 // if we get here we didn't hit above return so we didn't find target
20 return -1;
21}
22
23function splitWords(s) {
24 return s === "" ? [] : s.split(" ");
25}
26
27function* main() {
28 const arr = splitWords(yield).map((v) => parseInt(v));
29 const target = parseInt(yield);
30 const res = binarySearch(arr, target);
31 console.log(res);
32}
33
34class EOFError extends Error {}
35{
36 const gen = main();
37 const next = (line) => gen.next(line).done && process.exit();
38 let buf = "";
39 next();
40 process.stdin.setEncoding("utf8");
41 process.stdin.on("data", (data) => {
42 const lines = (buf + data).split("\n");
43 buf = lines.pop();
44 lines.forEach(next);
45 });
46 process.stdin.on("end", () => {
47 buf && next(buf);
48 gen.throw(new EOFError());
49 });
50}
511#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9int binary_search(std::vector<int> arr, int target) {
10 int left = 0;
11 int right = arr.size() - 1;
12
13 while (left <= right) { // <= here because left and right could point to the same element, < would miss it
14 int mid = left + (right - left) / 2; // use `(right - left) / 2` to prevent `left + right` potential overflow
15 // found target, return its index
16 if (arr.at(mid) == target) return mid;
17 if (arr.at(mid) < target) {
18 // middle less than target, discard left half by making left search boundary `mid + 1`
19 left = mid + 1;
20 } else {
21 // middle greater than target, discard right half by making right search boundary `mid - 1`
22 right = mid - 1;
23 }
24 }
25 return -1; // if we get here we didn't hit above return so we didn't find target
26}
27
28template<typename T>
29std::vector<T> get_words() {
30 std::string line;
31 std::getline(std::cin, line);
32 std::istringstream ss{line};
33 ss >> std::boolalpha;
34 std::vector<T> v;
35 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
36 return v;
37}
38
39void ignore_line() {
40 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
41}
42
43int main() {
44 std::vector<int> arr = get_words<int>();
45 int target;
46 std::cin >> target;
47 ignore_line();
48 int res = binary_search(arr, target);
49 std::cout << res << '\n';
50}
511use std::error;
2use std::io;
3use std::str::FromStr;
4
5fn binary_search(arr: Vec<i32>, target: i32) -> i32 {
6 let mut left = 0;
7 let mut right = arr.len();
8 while left < right {
9 let mid = left + (right - left) / 2;
10 if arr[mid] == target {
11 return mid as i32;
12 }
13 if arr[mid] < target {
14 left = mid + 1;
15 } else {
16 right = mid;
17 }
18 }
19 -1
20}
21
22fn main() -> Result<(), Box<dyn error::Error>> {
23 let mut line = String::new();
24 io::stdin().read_line(&mut line)?;
25 let arr = line
26 .split_whitespace()
27 .map(i32::from_str)
28 .collect::<Result<_, _>>()?;
29 let mut line = String::new();
30 io::stdin().read_line(&mut line)?;
31 let target = line.trim_end().parse()?;
32 let res = binary_search(arr, target);
33 println!("{}", res);
34 Ok(())
35}
361package main
2
3import (
4 "bufio"
5 "fmt"
6 "os"
7 "strconv"
8 "strings"
9)
10
11func binarySearch(arr []int, target int) int {
12 left := 0
13 right := len(arr) - 1
14
15 for left <= right { // <= here because left and right could point to the same element, < would miss it
16 mid := left + (right-left)/2 // use `(right - left) / 2` to prevent `left + right` potential overflow
17 // found target, return its index
18 if arr[mid] == target {
19 return mid
20 }
21 if arr[mid] < target {
22 // middle less than target, discard left half by making left search boundary `mid + 1`
23 left = mid + 1
24 } else {
25 // middle greater than target, discard right half by making right search boundary `mid - 1`
26 right = mid - 1
27 }
28 }
29 return -1 // if we get here we didn't hit above return so we didn't find target
30}
31
32func arrayAtoi(arr []string) []int {
33 res := []int{}
34 for _, x := range arr {
35 v, _ := strconv.Atoi(x)
36 res = append(res, v)
37 }
38 return res
39}
40
41func splitWords(s string) []string {
42 if s == "" {
43 return []string{}
44 }
45 return strings.Split(s, " ")
46}
47
48func main() {
49 scanner := bufio.NewScanner(os.Stdin)
50 scanner.Scan()
51 arr := arrayAtoi(splitWords(scanner.Text()))
52 scanner.Scan()
53 target, _ := strconv.Atoi(scanner.Text())
54 res := binarySearch(arr, target)
55 fmt.Println(res)
56}
571def binary_search(arr, target)
2 left = 0
3 right = arr.length - 1
4 # <= because left and right could point to the same element, < would miss it
5 while left <= right
6 mid = (left + right) / 2
7 # found target, return its index
8 return mid if arr[mid] == target
9 if arr[mid] < target
10 # middle less than target, discard left half by making left search boundary `mid + 1`
11 left = mid + 1
12 else
13 # middle greater than target, discard right half by making right search boundary `mid - 1`
14 right = mid - 1
15 end
16 end
17 # if we get here we didn't hit above return so we didn't find target
18 -1
19end
20
21if __FILE__ == $0
22 arr = gets.split.map { |v| Integer(v, 10) }
23 target = Integer(gets, 10)
24 res = binary_search(arr, target)
25 puts(res)
26end
271#lang racket
2
3(define (binary-search arr target)
4 (let search ([l 0]
5 [r (sub1 (vector-length arr))])
6 ;; <= because left and right could point to the same element, < would miss it
7 (if (<= l r)
8 (let* ([m (quotient (+ l r) 2)]
9 [v (vector-ref arr m)])
10 (cond
11 ;; found target, return its index
12 [(= v target) m]
13 ;; middle less than target, discard left half by making left search boundary `m + 1`
14 [(< v target) (search (add1 m) r)]
15 ;; middle greater than target, discard right half by making right search boundary `m - 1`
16 [else (search l (sub1 r))]))
17 ;; if we get here we didn't hit above guard so we didn't find target
18 -1)))
19
20(define arr (list->vector (map string->number (string-split (read-line)))))
21(define target (string->number (read-line)))
22(define res (binary-search arr target))
23(displayln res)
241import Data.Array (Array)
2import Data.Array.IArray (bounds, listArray)
3import qualified Data.Array.IArray as A
4
5binarySearch :: Array Int Int -> Int -> Int
6binarySearch arr target = uncurry search $ bounds arr
7 where
8 search l r
9 -- <= because left and right could point to the same element, < would miss it
10 | l <= r = case compare (arr A.! m) target of
11 -- found target, return its index
12 EQ -> m
13 -- middle less than target, discard left half by making left search boundary `m + 1`
14 LT -> search (succ m) r
15 -- middle greater than target, discard right half by making right search boundary `m - 1`
16 GT -> search l (pred m)
17 -- if we get here we didn't hit above guard so we didn't find target
18 | otherwise = -1
19 where
20 -- use `(r - l) / 2` to prevent `l + r` potential overflow
21 m = l + (r - l) `div` 2
22
23main :: IO ()
24main = do
25 arr' <- map read . words <$> getLine
26 let arr = listArray (0, length arr' - 1) arr'
27 target <- readLn
28 let res = binarySearch arr target
29 print res
30Calculating mid
Note that when calculating mid, if the number of elements is even, there are two elements in the middle. We usually follow the convention of picking the first one, equivalent to doing integer division (left + right) / 2.
In most programming languages, we calculate mid with left + floor((right-left) / 2) to avoid potential integer overflow. However, in Python, we do not need to worry about integer overflow with left + right because Python3 integers can be arbitrarily large.
Deducing binary search
It's essential to understand and deduce the algorithm yourself instead of memorizing it. In an actual interview, interviewers may ask you additional questions to test your understanding, so simply memorizing the algorithm may not be enough to convince the interviewer.
Key elements in writing a correct binary search:
1. When to terminate the loop
Make sure the while loop includes an equality comparison; otherwise, we might skip the loop and miss the potential match for the edge case of a one-element array.
2. Whether/how to update left and right boundary in the if conditions
Consider which side to discard. If arr[mid] is smaller than the target, we should discard everything on the left by making left = mid + 1.
3. Should I discard the current element?
For vanilla binary search, we can discard it since it cannot be the final answer if it is not equal to the target. There might be situations where you would want to think twice before discarding the current element. We'll discuss this in the next module.
When to use binary search
Interestingly, binary search works beyond sorted arrays. You can use binary search whenever you make a binary decision to shrink the search range. We will see this in the following modules.
P.S. Did you notice AlgoMonster's logo is an illustration of binary search? :P