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.

Updated on 29/9/2021

## 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

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:

#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)

else

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

return 0;

}

Binary search if an array is sorted in descending order:

#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)

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

else

Print data found at position pos+1

Step 6: Stop

## Linear search program:

#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)

else

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

return 0;

}

In the upcoming post, you will be getting information related to selection sort and bubble sort and 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. 