Binary Search Algorithm with EXAMPLE

Before we learn Binary search, let's learn:

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 to 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.

In this algorithm tutorial, you will learn:

• What is Search?
• What is Binary Search?
• How Binary Search Works?
• Example Binary Search
• Why Do We Need Binary 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 searches analyses the upper values to the middle element for comparison and matching
• In case the key value is greater than the middle element then searches analyses the lower values to the middle element for comparison and matching

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 – 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 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 the 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 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

Summary

• Search is a utility that enables its user to search for documents, files, and other types of data. A binary search is an advanced type of search algorithm that finds and fetches data from a sorted list of items.
• Binary search is commonly known as a half-interval search or a logarithmic search
• It works by dividing the array into half on every iteration under the required element is found.
• The binary algorithm takes the middle of the array by dividing the sum of the left and rightmost index values by 2. Now, the algorithm drops either the lower or upper bound of elements from the middle of the array, depending on the element to be found.
• The 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 than using equality comparisons that are slow and inaccurate.
• A binary search is not suitable for unsorted data.