Table of contents
- Q1. Implement Binary Search and use it to find an element in a sorted array.
- Q2. Solve the "find the first and last position of an element in a sorted array" problem.
- Q3. Solve the "search in a rotated sorted array" problem.
- Q4. Solve the "find the square root of a number" problem using binary search.
- Q5. Implement a program to find the peak element in an array using binary search.
Today, I focused on mastering searching algorithms, particularly Binary Search. I implemented Binary Search to find elements in sorted arrays and tackled problems like finding the first and last position of an element in a sorted array. I also solved challenges like searching in a rotated sorted array, finding the square root of a number using binary search, and identifying the peak element in an array. These problems gave me valuable insights into efficient search techniques for different scenarios.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement Binary Search and use it to find an element in a sorted array.
#include <iostream>
using namespace std;
void binarySearch(int arr[], int size, int k, int low, int high){
int mid=(low+high)/2;
if(k==arr[mid]){
cout<<"The element is present at position: "<<mid+1;
}
else if(k<arr[mid]){
high=mid-1;
binarySearch(arr,size,k,low,high);
}
else if(k>arr[mid]){
low=mid+1;
binarySearch(arr,size,k,low,high);
}
}
int main()
{
int n,k;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<"Enter the element to be searched: ";
cin>>k;
int low=0;
int high=n-1;
binarySearch(arr,n,k,low,high);
return 0;
}
This code implements the Binary Search algorithm to find an element k in a sorted array. It uses a recursive approach where the binarySearch function takes the array, its size, the target element k, and the current search boundaries (low and high). The middle index (mid) is calculated, and if the element at mid matches k, its position is printed. If k is smaller than the element at mid, the search continues in the left half by adjusting the high pointer. If k is larger, the search moves to the right half by adjusting the low pointer. The process repeats recursively until the element is found. The program prints the position of the element, indexed from 1.
Q2. Solve the "find the first and last position of an element in a sorted array" problem.
#include <iostream>
using namespace std;
int findFirst(int arr[],int low, int high,int k){
if(low>high){ // Base case: element not found
return -1;
}
int mid=low+(high-low)/2; // Calculate middle index
if(k==arr[mid]){ // If the element is found
// Check if it's the first occurrence
if(mid==0 || arr[mid-1]!=k){
return mid;
}
else{
return findFirst(arr,low,mid-1,k); // Search in the left half
}
}
else if(k<arr[mid]){ // If k is smaller, search in the left half
return findFirst(arr,low,mid-1,k);
}
else if(k>arr[mid]){ // If k is larger, search in the right half
return findFirst(arr,mid+1,high,k);
}
}
int findLast(int arr[],int low, int high,int k){
if(low>high){ // Base case: element not found
return -1;
}
int mid=low+(high-low)/2; // Calculate middle index
if(k==arr[mid]){ // If the element is found
// Check if it's the last occurrence
if(mid==high || arr[mid+1]!=k){
return mid;
}
else{
return findLast(arr,mid+1,high,k); // Search in the right half
}
}
else if(k<arr[mid]){ // If k is smaller, search in the left half
return findLast(arr,low,mid-1,k);
}
else if(k>arr[mid]){ // If k is larger, search in the right half
return findLast(arr,mid+1,high,k);
}
}
int main()
{
int n,k;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<"Enter the element to be searched: ";
cin>>k;
int high=n-1;
int low=0;
cout<<"The first occurrence is at index: "<<findFirst(arr,low,high,k)<<endl;
cout<<"The last occurrence is at index: "<<findLast(arr,low,high,k)<<endl;
return 0;
}
This code solves the problem of finding the first and last occurrence of a given element k in a sorted array using binary search. The findFirst function searches for the first occurrence of k by checking if the element at the middle index mid is equal to k. If it is, the function checks if it is the first occurrence by ensuring that the previous element is not equal to k. If it is not the first occurrence, the function recursively searches the left half of the array. Similarly, the findLast function finds the last occurrence by checking if the element at mid is equal to k and then ensures that the next element is different to confirm it's the last occurrence, recursively searching the right half if needed.
Q3. Solve the "search in a rotated sorted array" problem.
#include <iostream>
using namespace std;
void searchInRotatedArray(int arr[],int size,int k,int low,int high) {
if(low>high) {
cout<<"The element is not present in the array.";
return;
}
int mid=low+(high-low)/2;
if(arr[mid]==k) {
cout<<"The element is present at position: "<<mid+1;
return;
}
// Check which half is sorted
if (arr[low]<=arr[mid]) {
// Left half is sorted
if(k>=arr[low] && k<arr[mid]) {
searchInRotatedArray(arr,size,k,low,mid-1); // Search in the left half
}
else{
searchInRotatedArray(arr,size,k,mid+1,high); // Search in the right half
}
} else {
// Right half is sorted
if(k>arr[mid] && k<=arr[high]) {
searchInRotatedArray(arr, size, k, mid + 1, high); // Search in the right half
}
else{
searchInRotatedArray(arr, size, k, low, mid - 1); // Search in the left half
}
}
}
int main() {
int n, k;
cout << "Enter length of the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Enter the element to be searched: ";
cin >> k;
searchInRotatedArray(arr,n,k,0,n-1);
return 0;
}
This code solves the problem of searching for an element k in a rotated sorted array using a modified binary search algorithm. In a rotated sorted array, part of the array is sorted, but the array has been rotated, meaning the order of elements is disrupted around a pivot point. The searchInRotatedArray function works by first checking if the middle element mid matches the target element k. If not, it determines which half of the array is sorted by comparing the values at the low, mid, and high indices. If the left half is sorted (i.e., arr[low] <= arr[mid]), it checks if k lies within this range and recursively searches the left half; otherwise, it searches the right half. If the right half is sorted (i.e., arr[mid] < arr[high]), it similarly checks if k lies within this range and searches accordingly.
Q4. Solve the "find the square root of a number" problem using binary search.
#include <iostream>
using namespace std;
int squareRoot(int n,int low,int high){
if (low > high) { // Base case: if the range is invalid, return the high value as the floor of square root
return high;
}
int mid=low+(high-low)/2; // Calculate middle index
if(mid*mid==n){ // If mid is the exact square root
return mid;
}
else if(mid*mid<n){ // If mid squared is less than n, move towards higher half
return squareRoot(n,mid+1,high);
}
else if(mid*mid>n){ // If mid squared is greater than n, move towards lower half
return squareRoot(n,low,mid-1);
}
}
int main()
{
int n;
cout<<"Enter the number: ";
cin>>n;
cout<<"The square root is: "<<squareRoot(n,0,n);
return 0;
}
This code solves the problem of finding the square root of a given number n using binary search. The squareRoot function performs a binary search between the range low and high to find the integer part of the square root of n. It calculates the middle value (mid) and checks whether its square equals n. If it does, mid is returned as the square root. If the square of mid is less than n, the search continues in the higher half (mid+1 to high); otherwise, it continues in the lower half (low to mid-1). The base case occurs when the search range becomes invalid (i.e., low > high), in which case the function returns high as the integer part of the square root, effectively truncating any decimal part.
Q5. Implement a program to find the peak element in an array using binary search.
#include <iostream>
using namespace std;
int findPeak(int arr[],int low, int high){
int mid=low+(high-low)/2; // Calculate the middle index
if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1]){ // If mid is greater than both neighbors
return arr[mid]; // Peak element found
}
else if(arr[mid]<arr[mid+1]){ // If the right neighbor is greater, move towards right half
return findPeak(arr,mid+1,high);
}
else if(arr[mid]<arr[mid-1]){ // If the left neighbor is greater, move towards left half
return findPeak(arr,low,mid-1);
}
}
int main()
{
int n;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<"Peak element is: "<<findPeak(arr,0,n-1);
return 0;
}
This program finds the peak element in an array using binary search. A peak element is defined as an element that is greater than its neighbors. The findPeak function takes an array and performs a binary search to locate the peak element. The middle element arr[mid] is compared with its neighbors (arr[mid-1] and arr[mid+1]). If arr[mid] is greater than both neighbors, it is the peak, and the function returns it. If the element on the right (arr[mid+1]) is greater than arr[mid], the search continues in the right half of the array (from mid+1 to high), otherwise, it continues in the left half (from low to mid-1).
Today's practice reinforced my understanding of Binary Search and its versatility in solving a range of problems. From searching in sorted arrays to handling rotated arrays and square roots, I gained deeper insights into how binary search can be applied efficiently in various contexts. I'm excited to continue refining my skills in searching algorithms in the coming days!