Table of contents
- 1. To implement binary search and analyze its time complexity
- 2. Solve the "find the first and last position of an element in a sorted array" problem.
- 3. Solve the "search in a rotated sorted array" problem.
- 4. Solve the "find the square root of a number" problem using binary search.
- 5. Implement a program to find the peak element in an array using binary search.
Welcome to Day 13 of 100 Days of DSA challenge! Today, I solved five problems focused on binary search. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!
1. To implement binary search and analyze its time complexity
Binary search is the most important algorithm in computer science, in this we try to search an element target in a given array. The only condition is that the array must be sorted to search this element. We divide the array in two parts and search for the target in the part where it could potentially lie by comparing it with mid.
The time complexity of binary search is O(logn). It can be solved both iteratively and recursively. The recursive approach is however better.
Code:
#include<iostream>
using namespace std;
int recursiveBin(int arr[],int low,int high,int target){
if(low>high){
return -1;
}
int mid=(low+high)/2;
if(arr[mid]==target){
return mid;
}
else if(arr[mid]>target){
recursiveBin(arr,low,mid-1,target);
}
else{
recursiveBin(arr,mid+1,high,target);
}
}
int main(){
//sorted array
int arr[10]={34,45,56,67,78,90,101,123,124,144};
int target=101;
cout<<"The array is:"<<endl;
for(int i=0;i<10;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
int res=recursiveBin(arr,0,10,101);
if(res==-1){
cout<<"Element not found"<<endl;
}
else{
cout<<"Element found at index "<<res;
}
}
Output:
2. Solve the "find the first and last position of an element in a sorted array" problem.
In this problem we have to find the first and last occuring index of a given target element. Since the array is sorted we can apply binary search here. It can be applied twice, like two pass binary search. The first pass is for finding the first occurrence, second pass is for last occurrence. Duplicate elements are allowed and if the element does’nt exist we return {-1,-1}.
Code:
#include <iostream>
using namespace std;
void binarySearch(int arr[], int target, int size) {
int low = 0, high = size - 1;
int first = -1, last = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
first = mid;
high = mid - 1;
} else if (arr[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
low = 0, high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
last = mid;
low = mid + 1;
} else if (arr[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << "The first and last indexes of " << target << " are " << first << " and " << last << endl;
}
int main() {
int arr[8] = {1, 2, 3, 4, 4, 5, 6, 7};
int target = 4;
cout << "The array is:" << endl;
for (int i = 0; i < 8; i++) {
cout << arr[i] << " ";
}
cout << endl;
binarySearch(arr, target, 8);
return 0;
}
Output:
3. Solve the "search in a rotated sorted array" problem.
To solve the "Search in a Rotated Sorted Array" problem using binary search, we begin by initializing two pointers, low and high, to the start and end of the array, respectively. Then, calculate the middle element at index mid. If arr[mid] equals the target, return mid. If the left half is sorted (i.e., arr[low] <= arr[mid]), check if the target lies within the sorted left half; if it does, adjust high to mid - 1; otherwise, set low to mid + 1. If the right half is sorted, check if the target lies within that range, and adjust low or high accordingly. Repeat this process until the target is found or the pointers converge.
Code:
#include<iostream>
using namespace std;
int searchInRotatedArray(int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[low] <= arr[mid]) {
if (arr[low] <= target && target < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if (arr[mid] < target && target <= arr[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}
int main() {
int arr[] = {4, 5, 6, 7, 1, 2, 3};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 1;
int result = searchInRotatedArray(arr, size, target);
if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found!" << endl;
}
return 0;
}
Output:
4. Solve the "find the square root of a number" problem using binary search.
The square root of a number N, lies between 0 and N. We can apply binary search such that the low=0 and high=N. If the mid*mid is==N, then we return mid, otherwise we update low and high based on mid*mid.
Code:
// To find the square root of a number using binary search
#include<iostream>
using namespace std;
int squareRoot(int num){
int low=0;
int high=num;
int mid;
while(low<=high){
int mid=(low+high)/2;
if(mid*mid==num){
return mid;
}
else if(mid*mid>num){
high=mid-1;
}
else{
low=mid+1;
}
}
return high;
}
int main(){
int num;
cout<<"Enter the number:";
cin>>num;
cout<<"Square of "<<num<<" is "<<squareRoot(num)<<endl;
}
Output:
5. Implement a program to find the peak element in an array using binary search.
A peak element in an array is the one which is greater than its neighbouring elements, this problem can be solved using binary search. If the midis peak then we return it. Otherwise if arr[mid]<arr[mid+1] then we update low=mid+1, else we update high=mid-1.
Code:
// to find the peak element
#include<iostream>
using namespace std;
int peak(int arr[],int size){
int low=0;
int high=size-1;
while(low<=high){
int mid=low +(high-low)/2;
if(arr[mid]>=arr[mid-1] && arr[mid]>=arr[mid-1]){
return mid;
}
else if(arr[mid]<arr[mid+1]){
low=mid+1;
}
else{
high=mid-1;
}
}
return -1;
}
int main(){
int arr[7]={1,2,3,56,4,3,1};
int res=peak(arr,7);
cout<<"The peak element in array is:"<<arr[res];
}
Output:
So today was all about using binary search in different ways to solve these problems. Binary search is a really useful algorithm not only it’s implementation is simple, it saves time with O(logn) complexity. See you tomorrow! Happy Coding🍀