Binary Search Algorithm with EXAMPLE

Before we learn Binary search, let’s learn what search is.

What is Search?

Search is a utility that enables its user to find documents, files, media, or any other type of data held inside a database. Search works on the simple principle of matching the criteria with the records and displaying it to the user. In this way, the most basic search function works.

What is Binary Search?

A binary search is an advanced type of search algorithm that finds and fetches data from a sorted list of items. Its core working principle involves dividing the data in the list into half until the required value is located and displayed to the user in the search result. Binary search is commonly known as a half-interval search or a logarithmic search.

How Binary Search Works?

The binary search works in the following manner:

• The search process initiates by locating the middle element of the sorted array of data.
• After that, the key value is compared with the element.
• If the key value is smaller than the middle element, then the search analyses the upper values to the middle element for comparison and matching.
• In case the key value is greater than the middle element, then the search analyses the lower values to the middle element for comparison and matching.

Binary Search Algorithm (Pseudocode)

The binary search can be written as a short, iterative routine. It keeps two pointers, low and high, and narrows the range until the target is found or the range becomes empty.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

The routine returns the index of the target on success and -1 when the value is not present. Because the range halves on every pass, the loop runs at most log₂(n) times.

Example Binary Search

Let us look at the example of a dictionary. If you need to find a certain word, no one goes through each word in a sequential manner but randomly locates the nearest words to search for the required word.

The above image illustrates the following:

1. You have an array of 10 digits, and the element 59 needs to be found.
2. All the elements are marked with the index from 0 to 9. Now, the middle of the array is calculated. To do so, you take the left and rightmost values of the index and divide them by 2. The result is 4.5, but we take the floor value. Hence the middle is 4.
3. The algorithm drops all the elements from the middle (4) to the lowest bound, because 59 is greater than 24, and now the array is left with 5 elements only.
4. Now, 59 is greater than 45 and less than 63. The middle is 7. Hence the right index value becomes middle − 1, which equals 6, and the left index value remains the same as before, which is 5.
5. At this point, you know that 59 comes after 45. Hence, the left index, which is 5, becomes mid as well.
6. These iterations continue until the array is reduced to only one element, or the item to be found becomes the middle of the array.

Example 2

Let’s look at the following example to understand the binary search working.

1. You have an array of sorted values ranging from 2 to 20 and need to locate 18.
2. The average of the lower and upper limits is (l + r) / 2 = 4. The value being searched is greater than the mid, which is 4.
3. The array values less than the mid are dropped from the search, and values greater than the mid-value 4 are searched.
4. This is a recurrent dividing process until the actual item to be searched is found.

Why Do We Need Binary Search?

The following reasons make binary search a better choice to be used as a search algorithm:

• Binary search works efficiently on sorted data no matter the size of the data.
• Instead of performing the search by going through the data in a sequence, the binary algorithm randomly accesses the data to find the required element. This makes the search cycles shorter and more accurate.
• Binary search performs comparisons of the sorted data based on an ordering principle rather than using equality comparisons, which are slower and mostly inaccurate.
• After every cycle of search, the algorithm divides the size of the array into half; hence, in the next iteration, it will work only in the remaining half of the array.

Learn our next tutorial on Linear Search: Python, C++ Example.

Binary Search vs Linear Search

Binary search and linear search are the two most common ways to find a value in a collection. The table below highlights how they differ:

In short, binary search is much faster on large sorted data, while linear search is simpler and the only option when the data is not sorted.

FAQs