Write a C, C++ program to implement a binary search. Binary search is an efficient search algorithm as compared to linear search. Let's implement this algorithm in C, C++.
Binary search is a search algorithm that finds the position of an element (target value) within a sorted array. It is also known as half-interval search or logarithmic search.
Important Points
i) Always use binary search with sorted values (either in asc or desc order).
Bubble sort algorithm and their implementation
Quicksort algorithm and their implementation
ii) Time complexity of binary search.
Best case performance - O(1)
Average and worst case time complexity - O(logn)
Binary Search using Recursion in C, C++
Sorting algorithm and their time complexity
Output:
Enter the size of an array : 7
Enter the values in sorted order (asc or desc) :
3 5 6 8 9 12 13
Enter a value to be search : 6
Item found at position : 3
Output :
Enter the size of an array (Max 100) : 5
Enter the elements of an array in asc or desc order : 2 3 6 7 8
Enter the elements to be searched in an array : 7
Number is found at 4 position
Programming questions on Strings
Programming questions on Recursion
Programming questions on Array
Programming questions on Linked List
Binary Search
Binary search is a search algorithm that finds the position of an element (target value) within a sorted array. It is also known as half-interval search or logarithmic search.
Important Points
i) Always use binary search with sorted values (either in asc or desc order).
Bubble sort algorithm and their implementation
Quicksort algorithm and their implementation
ii) Time complexity of binary search.
Best case performance - O(1)
Average and worst case time complexity - O(logn)
Binary Search using Recursion in C, C++
Sorting algorithm and their time complexity
Binary Search Algorithm
low = 0;
high = size - 1;
while (low <= high) {
/* Calculate mid index */
mid = (low + high) / 2;
/* If element is found at mid index
then return the index */
if (arr[mid] == num ) {
return mid+1;
} else if ( arr[mid] > num) {
high = mid - 1;
} else if ( arr[mid] < num) {
low = mid + 1;
}
}
/* If element is not found return -1 */
return -1;
Binary Search Program in C++
#include<iostream.h>
#include<conio.h>
void main()
{
int arr[100],beg,mid,end,i,n,num;
cout << "\n Enter the size of an array ";
cin >> n;
cout << "\n Enter the values in sorted order (asc or desc) \n";
for(i = 0; i < n;i++)
{
cin >> arr[i];
}
/* Initialize beg and end value. */
beg = 0;
end = n-1;
cout << "\n Enter a value to be searched in an array ";
cin >> num;
/* Run loop, while beg is less than end. */
while( beg <= end)
{
/* Calculate mid. */
mid = (beg+end)/2;
/* If value is found at mid index,
the print the position and exit. */
if(arr[mid] == num)
{
cout << "\nItem found at position "<< (mid+1);
exit(0);
} else if(num > arr[mid]) {
beg=mid+1;
} else if (num < arr[mid]) {
end=mid-1;
}
}
cout << "Number does not found.";
}
Output:
Enter the size of an array : 7
Enter the values in sorted order (asc or desc) :
3 5 6 8 9 12 13
Enter a value to be search : 6
Item found at position : 3
Binary Search Program in C
#include <stdio.h>
/* Search number in an array using binary search algorithm */
int binarySearch (int arr[], int num, int size) {
int low, high, mid;
low = 0;
high = size - 1;
while (low <= high) {
/* Calculate mid index */
mid = (low + high) / 2;
/* If element is found at mid index
then return the index */
if (arr[mid] == num ) {
return mid+1;
} else if ( arr[mid] > num) {
high = mid - 1;
} else if ( arr[mid] < num) {
low = mid + 1;
}
}
return -1;
}
int main(void) {
int arr[100], len, num, result;
printf(" \n Enter the size of an array (Max 100)");
scanf ("%d", &len);
printf("\n Enter the elements of an array in asc or desc order");
/* Taking array input values from user */
for (int i = 0; i < len; i++) {
scanf ("%d", &arr[i]);
}
printf ("\n Enter the elements to be searched in an array");
scanf ("%d", &num);
result = binarySearch (arr, num, len);
if (result == -1) {
printf (" \n Number is not found in an array");
} else {
printf (" \n Number is found at %d position", result );
}
return 0;
}
Output :
Enter the size of an array (Max 100) : 5
Enter the elements of an array in asc or desc order : 2 3 6 7 8
Enter the elements to be searched in an array : 7
Number is found at 4 position
Programming questions on Strings
Programming questions on Recursion
Programming questions on Array
Programming questions on Linked List
#include
ReplyDeletefor exit(0) function
process.h
DeleteThanks!
DeleteThanks
ReplyDeleteI am glad that this code helps you.
Deletei only understand binary search from this
ReplyDeleteI understand binary search only from this
ReplyDeleteWhat is the worst case of binary search Algorithm?
ReplyDeleteWorst case of binary search occur when element you are searching is not present in array or list.
Deletehelps me
ReplyDeleteWhat kind of help do you need in Binary Search program.
Deletewhat is the expected output ?
ReplyDeleteWhat's the input you are entering.
Deleteis 'loc' of the input value not required to find the position ?
ReplyDeletenice post
ReplyDeleteI couldn't figure out the last few lines of the code, pls help me
ReplyDeleteI couldn't figure out the logic of what happens if num>Arr[mid] pls help me!!
ReplyDeleteIf num > arr[mid] then set beg flag to mid + 1 as number is greater than mid so you will search the item in second halve.
DeleteNo, choice of variable is our choice, we can choose any name of the variable
ReplyDeleteUse stdlib.h for exit 0 function
ReplyDeleteUse stdlib.h for exit 0 function
ReplyDeleteWhat about dealing with string arrays or char arrays??
ReplyDeletethis binary search code is wrong
ReplyDeleteyou can't write mid=(low+high)/2 . It will create overflow.Assume that you have an array of size 2^32 and low = 2^32-2 and high = 2^32-1 so low +high will create overflow .
So the correct code will be mid = low+(high-low)/2;
but why
DeleteThanks man, it was great help!!
ReplyDeletewhat if we have two same numbers at different positions in an array and we want to find the position of both using BS??????
ReplyDeletea program that input a ten number by user and search a number given by user by using binary search.
ReplyDeletewrite a program that input a number by user and search number given by user by using binary search .
ReplyDelete#include
Deleteusing namespace std;
main()
{
int beg,mid,end,i,n,num;
int a[10]={4,5,6,7,8,9,10,11,14,15};
//initialize the beg & end value
beg=0;
end=10-1;
cout<<"/n entr the value to search :";
cin>>num;
//run loop when bega[mid])
{
beg=mid+1;
}
else if(num<a[mid])
{
end=mid-1;
}
else
cout<<"not found";
}
}
Thanks for helping last cout<<"number not found" became before the close bracket in this way:
ReplyDeleteend=mid-1;
}
else
cout<<"number not found";
}
}
Binarey search in C++
nice solution
ReplyDeleteIn the case of beg>end the ouptput is not found number in list etc...but in same case is it possible to use the do...while loop or switch case for change the value of *end* for take some value in output..?
ReplyDeleteIf is it possible plzz give code for it.
1-i dont understand why you made while loop low<=end
ReplyDelete2-why you made equale in while loop
3- what is the exit(0)? what does it make ?!
1- i didn't understand why you made while loop low<=high ?
ReplyDelete2- why you made equale in while loop?
3- what is the function exit(0)? what does it mean and what can i do by using it ?
Does not work "at all" in descending order.
ReplyDelete