Binary Search in Arrays C++ | Searching in C++

Searching in C++

What is Linear Search?

linear search or sequential search is a method for finding a target value within a array. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

What is Binary Search?

Binary Search also known as half-interval search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.

There is an important condition in this type of searching which is that your array should be sorted.

Sort:the act of separating things and putting them in a particular order. And here sorted means that its elements should be in ascending or descending order.Although i prefer the ascending order but you can use descending order also. You can also take the presorted array but i have provided the algorithm of sorting in this program. But i’ll also write another post about sorting also.

Sorted Array,Techmenology
Searching in Sorted Arrays

 

Logic:

In this type of searching you have to divide the array into two parts by finding the mid value. If the middle value if equals to your  desired value then your search ends. But if the desired value is greater than the mid value then the upper  half is again divided into two parts and this step is repeated until  the mid value is not equals to desired value. Now if the desired value is smaller than the mid value then the lower half is again divided into two parts and this step is repeated until  the mid value is not equals to desired value.

code:

This is a well commented code i’ve even commented about very simple steps

#include <iostream>
#include <string>

using namespace std;

int main () {
int a[5]={4,1,2,3,5}; // Declaring of array
int temp;
//For sorting the array in Ascending order using bubble sort

for(int i=0;i<5;i++) {
for(int j=0;j<4;j++) {
if (a[i]<a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}

//The Searching logic begins here if you want only to practice searching logic then take sorted array and run the program below

int mid,beg=0,end=4,item=2;
cout << “Enter Your item: “<<endl;

cin>>item; //Getting the input value that you want to search

mid=int(beg+end)/2; //Formula to find middle value

if (item > a[end] && item<a[beg]){ //Condition that if the last value is smaller than the input value

cout << “Sorry Item not found”;

}

while (beg<=end && a[mid]!=item) { //Starting loop with condition that run untill beginning of array is less than or equal to end of the array  and the middle value of array is not equal to input value

if(a[mid] > item) { // condition is if the middle index’s values it greater than the input value

end=mid-1; //if conditions satisfies then the end becomes middle index minus one

}else{
end=mid+1; //  if the middle index’s values it smaller than the input value then end becomes middle index plus one
}
mid=int(beg+end)/2; //again calculating middle with new values
}
if (a[mid]==item) { //condition if the middle value is equals to input value
cout << “Item found at index: “<<mid;
} else {
cout << “item not found”<<endl;
}

return 0;
}

 

Conclusion:

I have used two algorithms at the same time to make my code efficient. But if want just Searching Algorithm then leave the sorting algorithm. But this is the most efficient way in binary Searching.

If you guys have any questions about this then tell me in the comments please

Thanks 😊

6 Comments

Add a Comment

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