Binary Search algorithm

Basics

The main requirement for the binary search is: Array must be sorted.

The binary search work in the same way as searching phone number by person name in phonebook.

Or similar to searching word in the dictionary.

For example you need to find word “Mars”. What the steps people usually do:

1. Open the dictionary in the middle and check any word
2. If the word started from “P” then the word “Mars” located in the first part of the book.
3. Then you divide the first part of the book and check the next word.
4. The next word can start from “G”.
5. In this case we need search second part of the first part of the book.

So, the range for the search becomes 2 times less every step.

The algorithm time complexity is O(log n)

See the illustration below:

Video with binary search in action

Diagrams

Loop implementation

Recursively implementation

Sample code

Below you will get a link to GitHub repo with Kotlin, Java, and Python source code