<commit_before>---
title: Binary Search
---

## Binary Search

A binary search locates an item in a sorted array by repeatedly dividing the search interval in half.

How do you search a name in a telephone directory?

One way would be to start from the first page and look at each name in the phonebook till we find what we are looking for. But that would be an extremely laborious and inefficient way to search.

Because we know that names in the phonebook are sorted alphabetically, we could probably work along the following steps:

1. Open the middle page of the phonebook
2. If it has the name we are looking for, we are done!
3. Otherwise, throw away the half of the phonebook that does not contain the name
4. Repeat until you find the name or there are no more pages left in the phonebook

Time complexity: As we dispose off one part of the search case during every step of binary search, and perform the search operation on the other half, this results in a worst case time complexity of *O*(*log<sub>2</sub>N*).
The best case occurs when the element to be found is in the middle of the list. The best case time complexity is *O*(*1*).

Space complexity: Binary search takes constant or *O*(*1*) space meaning that we don't do any input size related  variable defining.

for small sets linear search is better but in larger ones it is way more efficient to use binary search.

In detail, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

```
1 = N / 2^x
```

Multiply by 2<sup>x</sup>:

```
2^x = N
```

Now do the log2:

```<commit_msg>Add a gif showing binary search and linear search (#32384)<commit_after>---
title: Binary Search
---

## Binary Search

A binary search locates an item in a sorted array by repeatedly dividing the search interval in half.

How do you search a name in a telephone directory?

One way would be to start from the first page and look at each name in the phonebook till we find what we are looking for. But that would be an extremely laborious and inefficient way to search.

Because we know that names in the phonebook are sorted alphabetically, we could probably work along the following steps:

1. Open the middle page of the phonebook
2. If it has the name we are looking for, we are done!
3. Otherwise, throw away the half of the phonebook that does not contain the name
4. Repeat until you find the name or there are no more pages left in the phonebook

[![Binary vs Linear Search](https://www.mathwarehouse.com/programming/images/binary-vs-linear-search/binary-and-linear-search-animations.gif)]

Time complexity: As we dispose off one part of the search case during every step of binary search, and perform the search operation on the other half, this results in a worst case time complexity of *O*(*log<sub>2</sub>N*).
The best case occurs when the element to be found is in the middle of the list. The best case time complexity is *O*(*1*).

Space complexity: Binary search takes constant or *O*(*1*) space meaning that we don't do any input size related  variable defining.

for small sets linear search is better but in larger ones it is way more efficient to use binary search.

In detail, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

```
1 = N / 2^x
```

Multiply by 2<sup>x</sup>:

```
2^x = N
```

Now do the log2:

```
{'fraction_non_alphanumeric': 0.059722615341069915, 'fraction_numerical': 0.0093405038211152, 'mean_word_length': 3.9565217391304346, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7249569', 'n_tokens_mistral': 956, 'n_tokens_neox': 904, 'n_words': 601}