Binary Search in C++
What is binary search in C++?
What is binary search in C++?
Binary search is another searching algorithm in C++. It is also known as half interval search algorithm. It is an efficient and fast searching algorithm.
- The only condition required is that the elements in the list must be in sorted order.
- It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one.
How Binary Search Works in C++ (Simple Explanation):
- The list must be sorted in either ascending or descending order.
- Calculate the middle index using a formula.
- If the target element matches the middle element, the search stops.
- If the target is greater than the middle element, search the right half of the list.
- If the target is smaller, search the left half of the list.
- Repeat steps 3, 4, and 5 until the element is found or the list is fully checked.
Space and Time Complexity
Time Complexity (Best) | Ω(1) |
Time Complexity (Avg) | Θ(log n) |
Time Complexity (Worst) | O(log n) |
Space Complexity | O(1) |
Algorithm for Binary Search
- while(left<=right)
mid=left + (right – left)/2; - if(a[mid]<item)
left=mid+1; - else if(a[mid]>item)
right=mid-1; - If found return index+1
- Else return -1
Methods Discussed Here:
We will take a look at two different approaches
- Recursive Approach
- Iterative Approach
1. Binary Search (Recursive Approach)
// Binary Search implimentation in C++ (Recursive) // Time Complexity : O(N) // Space Complexity : O(1) // Auxiliary Space Complexity : O(N) due to function call stack #include<bits/stdc++.h> using namespace std; int binarySearch(int array[], int left, int right, int item){ if (right >= left){ // calculation of new mid int mid = left + (right - left)/2; // returns position where found if (array[mid] == item) return mid+1; // goes to recursive calls in left half if (array[mid] > item) return binarySearch(array, left, mid-1, item); // goes to recursive calls in right half else return binarySearch(array, mid+1, right, item); } // if element is not found we return -1 else return -1; } int main(){ int array[10] = {3, 5, 7, 9, 12, 15, 16, 18, 19, 22}; int item = 15; int position = binarySearch(array, 0, 10, item); if(position == -1) cout<<"Not Found"; else cout<<"We found the item "<< item <<" at position "<< position; }
Output:
We found the item 15 at position 6
2. Binary Search (Iterative Approach)
This one is simple too let’s have a look at this approach to solve binary search.
// Binary Search implimentation in C++ (Iterative) // Time Complexity : O(N) // Space Complexity : O(1) #include<bits/stdc++.h> using namespace std; // Returns index of item in given array, if it is present // otherwise returns -1 int binarySearch(int arr[], int l, int r, int item) { while (l <= r) { int mid = l + (r - l) / 2; // if item is at mid if (arr[mid] == item) return mid; // If item greater, ignore left half, consider only right half if (arr[mid] < item) l = mid + 1; // If item is smaller, ignore right half, consider only left half else r = mid - 1; } // if we are able to reach here // means item wasn't present return -1; } int main() { // array needs to be sorted to impliment binary search int arr[] = {3, 5, 7, 9, 12, 15, 16, 18, 19, 22}; int n = sizeof(arr) / sizeof(arr[0]); int item = 7; int position = binarySearch(arr, 0, n - 1, item); if(position == -1) cout << item << " Not Found"; else cout << item << " Found at index " << position; return 0; }
Output
7 Found at index 2
Advantages and Disadvantages of Binary Search
Advantages | Disadvantages |
---|---|
Efficient for large, sorted datasets; Reduces search space by half in each step; Time complexity of O(log N). | Requires the data to be sorted beforehand. |
Simple implementation using iterative or recursive approach. | Not suitable for unsorted data; Additional sorting step increases overall time complexity. |
Optimized for search operations in sorted arrays. | Recursive implementation can cause stack overflow for large datasets. |
You can also study binary search in C and Java:
You can also study binary search in C and Java:
FAQ's Related to Binary Search In C++
Answer:
Binary Search is a search algorithm that repeatedly divides a sorted array in half to locate a target value. It has a time complexity of O(log N).
Answer:
Use Binary Search when the dataset is sorted and you need to quickly find an element with minimal comparisons.
Answer:
Binary Search requires the dataset to be sorted beforehand. It is not suitable for unsorted data without sorting it first.
Answer:
The iterative approach uses a loop to search for the target, while the recursive approach uses function calls, which can lead to stack overflow for large datasets.
Login/Signup to comment