Welcome to Day 13 of the 100 Days of DSA challenge! Today, I tackled five thought-provoking problems that deepened my understanding of Binary Search and its practical applications. Binary Search is a powerful searching algorithm that simplifies problem-solving by efficiently narrowing down the search space. It’s a cornerstone technique used across various applications to optimize performance.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into the solutions and insights! 🚀
1. Binary Search
This program implements Binary Search to efficiently find a target element in a sorted array. It repeatedly divides the search range in half, comparing the middle element to the target. If the target matches the middle element, its index is returned. If the target is smaller, the search continues in the left half; if larger, in the right half. The process continues until the target is found or the range is exhausted, ensuring a logarithmic time complexity.
Code:
#include <iostream>
using namespace std;
// Function to perform Binary Search
int binary_search(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2; // Calculate the middle index
// Check if the middle element is the target
if (arr[mid] == target) {
return mid;
}
// If the target is smaller, search in the left half
if (arr[mid] > target) {
high = mid - 1;
}
// If the target is larger, search in the right half
else {
low = mid + 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7;
cout << "Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int result = binary_search(arr, 0, n - 1, target);
if (result != -1) {
cout << "Element " << target << " found at index " << result << endl;
} else {
cout << "Element " << target << " not found in the array." << endl;
}
return 0;
}
Output:
2. First and Last Positions of an Element in a Sorted Array
This program uses two separate Binary Search functions to find the first and last positions of a target value in a sorted array. The find_first function searches for the leftmost occurrence by narrowing the search range to the left half when the target is found. Similarly, the find_last function searches for the rightmost occurrence by narrowing the range to the right half. Both functions return the indices of the occurrences, or -1 if the target is not found.
Code:
#include <iostream>
using namespace std;
// Function to find the first occurrence of the target
int find_first(int arr[], int n, int target) {
int low = 0, high = n - 1;
int first = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
first = mid; // Update the first occurrence
high = mid - 1; // Search in the left half
} else if (arr[mid] > target) {
high = mid - 1; // Search in the left half
} else {
low = mid + 1; // Search in the right half
}
}
return first;
}
// Function to find the last occurrence of the target
int find_last(int arr[], int n, int target) {
int low = 0, high = n - 1;
int last = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
last = mid; // Update the last occurrence
low = mid + 1; // Search in the right half
} else if (arr[mid] > target) {
high = mid - 1; // Search in the left half
} else {
low = mid + 1; // Search in the right half
}
}
return last;
}
int main() {
int arr[] = {2, 4, 4, 4, 6, 6, 8, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 4;
cout << "Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int first = find_first(arr, n, target);
int last = find_last(arr, n, target);
if (first == -1) {
cout << "Element " << target << " not found in the array." << endl;
} else {
cout << "First occurrence of " << target << ": " << first << endl;
cout << "Last occurrence of " << target << ": " << last << endl;
}
return 0;
}
Output:
3. Search in a Rotated Array
The code performs a binary search on a rotated sorted array to find the target element. It identifies whether the left or right half of the array is sorted by comparing elements at the low, mid, and high indices. Based on the sorted half, it determines where the target might lie and narrows the search range accordingly. This process continues until the target is found or the range is exhausted, ensuring efficient logarithmic time complexity.
Code:
#include <iostream>
using namespace std;
// Function to perform binary search on a rotated sorted array
int rotated_array_search(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if the target is at mid
if (arr[mid] == target) {
return mid;
}
// Determine which half is sorted
if (arr[low] <= arr[mid]) {
// Left half is sorted
if (target >= arr[low] && target < arr[mid]) {
high = mid - 1; // Search in the left half
} else {
low = mid + 1; // Search in the right half
}
} else {
// Right half is sorted
if (target > arr[mid] && target <= arr[high]) {
low = mid + 1; // Search in the right half
} else {
high = mid - 1; // Search in the left half
}
}
}
return -1;
}
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 0;
cout << "Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int result = rotated_array_search(arr, 0, n - 1, target);
if (result != -1) {
cout << "Element " << target << " found at index " << result << endl;
} else {
cout << "Element " << target << " not found in the array." << endl;
}
return 0;
}
Output:
4. Square Root of a Number Using Binary Search
This program calculates the integer part of the square root of a given number using binary search. It iteratively narrows the range between 0 and the number by comparing the square of the middle value with the target. If the square of the middle value is less than the target, the result is updated, and the search continues to the right; otherwise, it moves to the left. Edge cases for 0, 1, and negative numbers are handled explicitly. The final result is the floor value of the square root.
Code:
#include <iostream>
using namespace std;
// Function to calculate the square root using binary search
int sq_root(int num) {
if (num < 0) {
return -1; // Square root is not defined for negative numbers
}
if (num == 0 || num == 1) {
return num; // Square root of 0 and 1 is the number itself
}
int low = 0, high = num;
int result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if mid * mid is equal to the number
if (mid * mid == num) {
return mid;
}
// If mid * mid is less than the number, move to the right half
if (mid * mid < num) {
result = mid; // Update result to track the floor value
low = mid + 1;
} else {
// If mid * mid is greater, move to the left half
high = mid - 1;
}
}
return result; // Return the floor of the square root
}
int main() {
int num = 25;
cout << "Finding the square root of: " << num << endl;
int sqrtResult = sq_root(num);
if (sqrtResult != -1) {
cout << "The floor of the square root of " << num << " is: " << sqrtResult << endl;
} else {
cout << "Square root is not defined for negative numbers." << endl;
}
return 0;
}
Output:
5. Peak Element in Array Using Binary Search
This program uses binary search to find a peak element in a given array. A peak element is one that is greater than or equal to its neighbors. The binary search works by checking the middle element and comparing it with its neighbors. If the middle element is a peak, it is returned. If not, the search space is narrowed based on whether the left or right neighbor is larger, moving towards the side where a peak might exist. The process continues until a peak element is found.
Code:
#include <iostream>
using namespace std;
// Function to find the peak element using binary search
int peak_element(int arr[], int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if mid is the peak element
if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == high || arr[mid + 1] <= arr[mid])) {
return mid; // Found peak element
}
// If the element on the left is greater, move to the left half
else if (mid > 0 && arr[mid - 1] > arr[mid]) {
high = mid - 1;
}
// If the element on the right is greater, move to the right half
else {
low = mid + 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 20, 4, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int peakIndex = peak_element(arr, 0, n - 1);
if (peakIndex != -1) {
cout << "Peak element is: " << arr[peakIndex] << " at index " << peakIndex << endl;
} else {
cout << "No peak element found." << endl;
}
return 0;
}
Output:
Day 13 was all about leveraging Binary Search to solve a variety of problems efficiently. The challenges showed how a simple yet powerful algorithm can be adapted for different scenarios, helping reduce time complexity to O(log n). With each problem, I reinforced my understanding of how to approach complex tasks in an optimized way. Excited to continue exploring more advanced algorithms tomorrow! 🚀