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?

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?

· Binary Search Algorithm.

· Linear Search Algorithm.

Here, in this tutorial, we will learn about Binary Search Algorithm in detail.

Binary Search Algorithm

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

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

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

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store