Skip to main content

Binary Search | The-Algorithm-Drive | MyCodingNetwork

Binary Search

The next algorithm, we are going to study is Binary Search. As the name suggests, it is a searching algorithm. It is one of the very famous searching techniques. Unlike its counterpart linear search, it is way more advanced. Time complexity of linear search is O(N) whereas that of binary search is O (log N).


Source Code:


Output

Number Found at index =5

Working

Let’s come on to the working of the algorithm, as you can see in the above program, we need a sorted array to perform binary search algorithm.

1.   Here, bin function in the above program it accepts 4 parameters, that is, the array arr, lower index low, higher index high and the searching number sn.

2.   Next, we have a do-while loop to check if high is greater than or equal to low (high>=low). If at any point of iteration this condition is not satisfied, it means the searching number sn does not exist in the array.

Following is the algorithm for binary search:

while(high>=low)
        {
           mid= (low+high)/2;
           /* mycodingnetwork.blogspot.com */
           if(sn==a[mid])
           return mid;
           else if(sn>a[mid])
            low=mid+1;
            else if(sn<a[mid])
            high=mid-1;
        }

 

3.   Inside the while loop, the mid variable calculates the middle index of the array. The formula used for this is (low+high)/2.

4.   The mid variable is followed by 3 conditional statements:

a.   In the first conditional statement if searching number is equal to middle index it returns mid as the answer.

b.   In the second condition, if searching number sn is greater than arr[mid], in this scenario low is changed to mid+1, since it is obvious that the searching number does not lie on the left side of the mid index.

c.    In the third condition, if searching number sn is lower than arr[mid], in this scenario high is changed to mid-1, since it is obvious that the searching number does not lie on the right side of the mid index.

The step 3 and 4 continues till high is greater than or equal to low, that is the condition of while loop, if this condition becomes false and no value is returned it means that the searching number does not exist in the given array therefore the exit the function will return -1. 


Hope you liked this explanation, for any doubt or feedback you can comment down in the comment section.


Labels:

Popular posts from this blog

Pattern 2 | Java

  Problem Statement: Write a program to draw the following pattern: * * * * * * * * * * * * * * * (take a variable n which decides the number of rows, for above example, n=5) THE CODE Output: *  * *  * * *  * * * *  * * * * *  * * * * * *          * * * * * * *        * * * * * * * *      * * * * * * * * *    * * * * * * * * * * Simplification : In the above problem, the value of n is 10 (i.e., the number of rows are 10) 1. In the first for loop we have i as the counter variable with initial value of 1 and having a condition i.e. i should be less than or equal to n.  It has a print statement after the second for loop,  System.out.println(); w hich is used for changing the row, each time for the second for loop terminates. 2. In the second for loop we have j as the counter variable with initial value of 1 having a condition i.e. j  should be  less than or equal to i (the value of i  will be as per the current ongoing iteration). Further it has an updation statement j++  Inside the seco
Discover More »

Code #1 | Hello Java | Basics of Java

Today starting with a very basic coding program in Java. So, the program is Write a program in Java to print "Hello Java!" Output: Hello Java!
Discover More »

Bubble Sort | Java & Python | MyCodingNetwork | Alok Tripathi

  Bubble Sort is a simple sorting algorithm that works by repeatedly comparing and swapping adjacent elements in an array until they are in the correct order. It is called bubble sort because the smaller elements "bubble" to the top of the array, while the larger elements sink to the bottom. Quick Video Explanation: How Bubble Sort Works Bubble sort works by iterating through the array from left to right and comparing each pair of adjacent elements. If the element on the left is larger than the element on the right, they are swapped. This way, the largest element in the array moves to the rightmost position in each iteration. This process is repeated until no more swaps are needed, which means the array is sorted. To illustrate how bubble sort works, let's use the example of sorting the array [30,90,50,10,40] in ascending order. First Iteration/Pass: The first step is to compare the first two elements, 30 and 90. Since 30 is smaller than 90, they are already i
Discover More »