Binary Search Algorithm
Binary Search Algorithm
Data Searching is an important task. However, there exist different algorithms that quickly search the given data. But in this tutorial, we will briefly discuss the binary search algorithm. But before moving to the Binary Search algorithm, let’s cover two essential things that are the part of the binary search:
1) What do you mean by Searching Algorithm?
2) What are two types of the Searching algorithm?
What do you mean by Searching Algorithm?
The searching algorithm is defined as the method of finding one or more than one element from a given set of data that is effective. This algorithm mostly finds the given elements from a specific data structure.
Moreover, Searching can be sequential or not; if the data in the given set are quite random, we need to use sequential Searching. Otherwise, an individual can use other different techniques to reduce the complexity.
What are the two types of Searching algorithms?
Generally, there are two types of the special Searching Algorithm that includes:
· Binary Search Algorithm.
· Linear Search Algorithm.
Here, in this tutorial, we will learn about Binary Search Algorithm in detail.
Binary Search Algorithm
Binary Search Algorithm is considered one of the most important types of searching algorithm. A binary search algorithm is a searching technique that usually works on sorted lists of elements effectively and efficiently. Therefore, to do any search from the given list of elements, it must be ensured that the list must be sorted effectively.
Moreover, the binary search usually uses or follows the effective approach called the Divide and Conquer. Firstly, the list is usually divided into two halves, and after that, the individual item is compared with an element of the list. If the element gets matched with the central element, the middle element’s location is received. If it is not matched, an individual will search for the next half.
Advantages of Binary Search
The Advantages of using the Binary Search Algorithm are as follows:
1) It usually eliminates the respective half of the list from the further searching by making use of the respective result from the comparison.
2) Compared with the linear search, the large lists of the data binary search is quite better.
3) The most important advantage of the binary search is that they usually indicate whether the element being searched is before or after the current position in the respective list.
Disadvantages of Binary Search
The disadvantages of the Binary Search Algorithm are as follows:
1) The main disadvantage of the Binary search algorithm is that it mainly employs the recursive approach that, in turn, requires more stack space.
2) The programming for the binary search algorithm is quite prone to error.
Working on the Binary Search Algorithm
Usually, the binary search algorithm can effectively be implemented in two ways respectively, which are as follows:
· Iterative Method.
· Recursive Method.
The recursive method is based on the divide and conquers approach.
The general steps involved in both methods are mainly described below.
1) Take the list of an array (Initial array) for which the Searching must be performed.
Initial Array
3
4
5
6
7
8
9
Consider y=4 to be the element to be get searched.
2) Set two pointers, low and high, at the lowest and highest positions, respectively.
Setting of pointers
3
4
5
6
7
8
9
Low High
3) In this step, we will find the middle element that is mid of the respective array.
The formula for calculating the middle of the array:
arr[low+high]/2.
arr[3+9]/2=6
Middle element.
3
4
5
6
7
8
9
Mid.
4) This comparison is made that if y==mid, it will return mid. Else compares the element that has to be searched with m.
5) And in the next step, if the y>mid, then compare y with the element’s respective middle element on the right side of the mid. This can be achieved by doing low to low=mid+1.
6) Otherwise, compare y with the respective middle element of the elements from the left side of the mid. This can be effectively achieved by setting high to high=mid-1.
Finding the middle element.
3
4
5
6
7
8
9
Low high
7) Repeat steps 3 to 6 until low meets high.
3
4
5
mid
8) y=4 is found successfully.
