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 6 | Java | MyCodingNetwork | Alok Tripathi (Code 8)

Problem Statement: Write a program to make a square and mark out its diagonals. Accept the length as input from the user and give output in the following manner: And ( In simple words, we have printed stars (*) on the boundary positions of the matrix and on the centre positions of the matrix we have printed blank space( ) )   THE CODE: Sample Output: In the above program, two int variables r to accept the length of square as input. On line 7, following statement is used to accept the input from the user: int r = sc . nextInt ();   For taking the input Scanner class has been used, more about Scanner class Algorithm: Two for loops are defined: ·         First for loop with counter variable i has initial value 1, conditional statement i less than or equal to r and an updating statement i++ . ·         Inside the first loop there is a second for loop, with counter variable j has ini...
Discover More »

YouTube Material 1| Hindi Video

Video Lecture- https://youtu.be/StCjnwfS0NQ Basic structure of a Java program public class xyz { public static void main(String args[]) { //Code //Code //Code //Code //Code }} public - access specifier/modifiers which makes the particular entity accessible throughout the program i.e., it can be accessed by other classes also. static - a keyword by which we don't have to create an object of that particular entity. void- return type keyword by which the function becomes non-returning type. main - name of the function String args[] - argument for main function Print Statement Syntax: System.out.println() ; Three types of Iteration statements are: for loop Example: for(int i=0; i<=5;i++) { //Code //Code //Code //Code //Code } The body of the above for loop will be executed 6 times. while loop( entry control loop) Syntax: while (condition) { //Code //Code //Code //Code //Code } The body of the above while loop will be executed continuously as long as the condition of the while is tr...
Discover More »

Pattern 1 | Java

Problem Statement: Write a program to draw the following pattern of NxN(where N is the input): * * * * * * * * * * * * * * * * * * * * * * * * * (here, N=5) THE CODE Output: Here, the input is 8 Simplification : In the above problem, two for loops are used: 1. The first for loop is having i as counter variable with  initial value of 1 and ending value of 10 with an updation statement i++. 2. The second for loop is having j as counter variable with initial value of 1 and ending value of 10 with an updation statement j++. The second  for loop is used to print  * in the respective column (the value of j represents the column number). It is having a print statement System.out.println("* ") to print * in each column(for convenience, I've added a space for better visibility of columns in the output). The first for loop is used to define rows( the value of i represents the row number). It is having a print statement System.out.print() to change rows each time the second for ...
Discover More »