Binary search is one of the most popular methods of locating a value in computer science. When it comes to a sorted array in a large database, it works perfectly. Usually, it is one of the most efficient search techniques. In today’s share from algo.monster, we will give a brief analysis of this technique. Hopefully, you will get a better understanding of it after finishing our article today.
A Short Introduction to Binary Search
Let’s start by learning the basics of this computer algorithm.
People often call binary search half-interval or logarithmic search. It is a search method that people use to locate the target value in a sorted array.
Binary search runs at the worst logarithmic speed, making O (log n) comparisons. where n represents the number of elements in an array, and the log is binary logarithm and uses only constant O(1)space.
How does this search method work?
This involves finding the element in the middle and comparing its key value to the element in that element. If the value is lower than the element at the middle, then you will need to search for the key to the list from the middle element to search for the other key.
Algorithm Binary Search
{( A[0 1 2 3…….n-1] , key) low 0 high n-1 while(low <= high) do (A[0 1 2 3 …….n-1] key) low high n-1 while (low = high), do m(low + high),/2 if (key=A[m]).
Algorithm return m else if (key<A[m]) then highß m-1 else lowß m+1 }
A sample of this search technique
Let 4,6,7,9 and 10, respectively, by the numbers given. The key is 9.
According to the algorithm, these numbers should be stored in a 1D array called A[0 2 n-1] where n= number elements. In this example, 5.
According to the algorithm, A[0 2 3 4] is created and the key value is passed into the array that is 9. Binary Search ( A[0 2 3 4] – 9 ) low=0 high=4 while (0=4)
Example Iteration 1 – m=2 low=3 //here Key=9 is greater than A[m]=7, so it executes the last other condition. Then, the loop of (34) will continue.
Iteration 2 – m=3 return 3.
Binary search time complexity
Let’s say we have an array of A. We are looking for K.
It takes, on average and in the worst cases, linear time, or O(N) to count the array items.
If A is a sorted array, however, Binary Search is faster to find K. Binary search cuts the length of the array after each iteration.
Time Analysis (recursive, iterative)
Binary Search can be analyzed with the average, worst, or best case number of comparisons. In fact, you do this analysis based on the length of the arrays. Suppose N=|A| is the length of Array A.
If comparison counting is slightly relaxed, the numbers of logarithmic search comparisons are equal.
Recursive binary search counts each pass through the If-then-else block as one comparison.
On the other hand, iterative logarithmic search counts each passes through the while blocks as one comparison.
Time Analysis for the Best Case
Best case – O (1) comparisons: In the ideal case, item X is located in the middle of array A. You will need to make a constant number of comparisons (actually, only 1)
Time Analysis for the Worst Case
Worst Case – O (log N) comparisons: In the worst scenario, item X is not found in array A. Binary Search reduces the permissible range by halving the size with each iteration or recursion. Ceiling (log n) can be used to halve the range. Ceiling (log n) comparisons are therefore required.
Time Analysis for the Average Case
Average case – O(log n) comparisons: To calculate the average case, multiply the number of comparisons needed to find each element by the probability of finding it. For simplicity, let’s assume that every item in A will be searched and that all probabilities of finding each element are equal.
Advantages and Disadvantages of the binary search algorithm
Advantage: Binary search is an efficient searching algorithm that allows us to find the desired element quickly. In fact, it is one of the quickest when it comes to sorted arrays within a larger database.
Disadvantage: One of the most annoying things about this method is that it is not suitable for unsorted arrays. In other words, you need to sort the elements in order before you can use this method. Actually, this is the only way to apply this search algorithm.
Binary Search Application: finding the word you want in a dictionary
Binary search is a powerful search tool that enables people to find desired records from a database. It often increases efficiency and saves time.
Below is a common application of this search algorithm in real life.
Surprisingly, but you can use it to easily spot any word you want to find. As we know, there are thousands of words in a dictionary. If you want to find some words, it takes a while. But with the help of a binary search algorithm, it’s a piece of cake.
For example, if you want to find the word “Voracious”. You can compare the middle page with the desired word first. If this word is alphabetically lower than the word on the middle page, we can stop searching from the higher part. That means, we can save half-time by only looking for it from the remaining left half. On the other hand, if it is bigger than the middle page word, similarly, we ignore the left half.
And the process won’t stop until you finally find the word you want.
Conclusion
If you carefully think about the example above, it’s easy to find out that the logarithmic search algorithm actually eliminates half of the elements each time. Thus, locating a single value from numerous numbers or a huge database saves time. Obviously, it saves much time.
For further information about search methods or other algorithms, you can check algo.monster out. They offer useful courses and lectures for beginners. Well, if you’re an expert already, you can still find something wonderful there. Enjoy your searching with a binary search algorithm.
