WAP to search an element in Array using "Binary Search".
Objective
Write a C++ program to search for an element using Binary Search.
Algorithm / Approach
- Initialize a PRE-SORTED array.
- Read the target
n. - Set
beg = 0andend = size - 1. - Run a loop
while (beg <= end). - Calculate the middle index:
mid = (beg + end) / 2. - If
ar[mid] == n, you found it! Break the loop. - If
ar[mid] < n, the target must be in the right half, so setbeg = mid + 1. - Otherwise, it's in the left half, so set
end = mid - 1.
main.cpp
#include<iostream>
using namespace std;
int main() {
int beg, end, mid, n;
int ar[9]={1,2,3,4,5,6,7,8,9};
cout<<"Enter no. to Search:";
cin>>n;
beg = 0;
end = 8;
while (beg <= end) {
mid = (beg+end)/2;
if(ar[mid] == n) {
cout<<"Found at "<< mid;
break;
}
else if(ar[mid] < n) {
beg = mid + 1;
}
else {
end = mid - 1;
}
}
if (beg > end)
cout<<"Not found!";
return 0;
}Expected Output
OUTPUT : 1 Enter no. to Search: 8 Found at 7 pos. OUTPUT : 2 Enter no. to Search: 17 Not found.
Explanation of the Program
- Binary Search is a highly efficient "divide and conquer" algorithm. It works like looking up a word in a dictionary: you open the book to the middle, decide if your word comes before or after that page, and then ignore the entire wrong half of the book.
- CRITICAL REQUIREMENT: Binary search ONLY works if the array is already sorted. If the array is jumbled, the algorithm's assumptions about which half to search will be completely wrong.
Complexity
Time Complexity
O(log n) - Extremely fast compared to O(n) for large datasets.
Space Complexity
O(1)
