Hey guys, what is up. In this particular post, we will be talking about linear and binary search algorithm. Also, about the source code and conditions.

Binary search explanation:

Binary search is used to find whether a given element is present in an array or not. Low is used to give the lower index and high to initialize the higher index. Pos is used to find the position of the data at which location. Pos is initialized with -1.  Array need to be sorted. Firstly the middle element location is found by using simple maths. Then the comparison of the middle element with the data is done. If the middle element and the data are equal then the program will terminate.

In another case, if the data is greater than the middle element then low is given a value equal to mid plus 1 and then the middle element is calculated and this process continues. If data is found lower than the middle element then the higher index is changed to mid minus 1. Pos is given the value of that location. Plus 1 is done because the array starts from 0. If pos is found equal to -1 then it indicates that data is not found.

Binary search algorithm:

Binary search algorithm for an array arranged in ascending order:

a[] is an array, where low, high, mid and pos are initialised

Step 1: low=0, high=n-1, pos=-1

Step 2: Repeat steps 3 and 4 while low <= high

Stair 3: mid= (low + high)/2

Step 4: if a[mid] = data

                        pos = mid

                        goto step 5

             else if data < a[mid]

                        high = mid-1

             else

                        low = mid + 1

            { End of loop }

Step 5: if pos = -1

                        Print data not found

             else

                        Print data found at position = (pos+1)

Step 6: Stop

Conditions for binary search:

To perform binary search in an array there are two necessary conditions:

  1. Array should be sorted either in ascending order or descending order.
  2. Middle element should be easily accessible.

Program:

binary search algorithm asc 1
binary search algorithm asc 2

#include <iostream.h>

#include<conio.h>

int main()

{

            clrscr();

            const max=20;

            int mid, low, pos, high, A[max], n, i, data;

            cout<<“Enter the dimension of array (<20)= “;

            cin>>n;

            cout<<“Enter elements in ascending order: “;

            for (i=0; i<n; i++)

            {

                        cout<<” A [“<<i<<“]= “;

                        cin>>A[i];

            }

            cout<<“Enter element you need to search= “;

            cin>>data;

//now giving values to low, high and pos

            low=0, high= n-1, pos=-1;

            while( low <= high)

            {

                        mid=(low+high)/2;

                        if ( A[mid] == data )

                        {

                                    pos=mid;

                                    break;

                        }

                        else if( data < A[mid] )

                                    high = mid-1;

                        else

                                    low = mid+1;

            }

            if (pos==-1)

                        cout<<“DATA NOT FOUND”;

            else

                        cout<<“DATA FOUND AT LOCATION= “<<pos+1;

            return 0;

}

Binary search if an array is sorted in descending order:

binary search algorithm des 1
binary search des 2

#include <iostream.h>

#include<conio.h>

int main()

{

            clrscr();

            const max=20;

            int mid, low, pos, high, A[max], n, i, data;

            cout<<endl<<endl<<“Enter the dimension of array (<20) “;

            cin>>n;

            cout<<“Enter elements in descending order: “;

            for (i=0; i<n; i++)

            {

                        cout<<” A [“<<i<<“]= “;

                        cin>>A[i];

            }

            cout<<“Enter element you need to search= “;

            cin>>data;

//now giving values to low, high and pos

            low=0, high= n-1, pos=-1;

            while( low <= high)

            {

                        mid=(low+high)/2;

                        if ( A[mid] == data )

                        {

                                    pos=mid;

                                    break;

                        }

                        else if( data > A[mid] )

                                    high = mid-1;

                        else

                                    low = mid+1;

            }

            if ( pos == -1)

                        cout<<“DATA NOT FOUND”;

            else

                        cout<<“DATA FOUND AT LOCATION= “<<pos+1;

            return 0;

}

Linear search explanation:

It is another method to find whether a given element is present in an array or not. It works on the simple method of checking each element one by one. If found then element location is printed. Otherwise, not found is printed. The array can be sorted or unsorted. There is no condition in sorting an array.

Linear search algorithm:

a[] is an array, where pos is initialised

Step 1: i=0, pos= -1

Step 2: Repeat steps 3 & 4 using while loop i<n (Condition)

Stair 3: if a[i] = data

                        pos=i

                        goto step 5

Step 4: i=i+1;

            { Ending of loop}

Step 5: if pos= -1

                        Print data not found

             else

                        Print data found at position pos+1

Step 6: Stop

Linear search program:

linear search 1
linear search algorithm 2

#include <iostream.h>

#include<conio.h>

int main()

{

            clrscr();

            const max=20;

            int  pos, A[max], n, i, data;

            cout<<“Enter the dimension of array (<20) “;

            cin>>n;

            cout<<“Enter elements: “;

            for (i=0; i<n; i++)

            {

                        cout<<” A [“<<i<<“]= “;

                        cin>>A[i];

            }

            cout<<“Enter element you need to search= “;

            cin>>data;

            i=0, pos= -1;

            while (i<n)

            {

                        if ( A[i] == data )

                        {

                                    pos=i;

                                    break;

                        }

                        i=i+1;

            }

            if ( pos == -1)

                        cout<<“DATA NOT FOUND”;

            else

                        cout<<“DATA FOUND AT POSITION= “<<pos+1;

            return 0;

}

In the upcoming post, you will be getting information related to some new types of sensors. If you haven’t seen our previous post on what is one-dimensional array and operations performed in them then go and read this. Also, you can read our previous posts by scrolling downwards. Also, stay tuned for the upcoming post.

Categories:

2 Comments

Mohit kashyap · May 17, 2021 at 2:11 pm

Good content

Sambhav Jain · May 18, 2021 at 11:51 am

Your content is amazing. Great effort by each and every individual involved in making it.
Keep it up.
Kudos

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *