Table of Contents
Problem Description:
Binary Search is a classic searching algorithm that efficiently finds the target element in a sorted array. Given a sorted array of integers nums and a target element target, you need to find the index of the target element in the array. If the target element is not present in the array, return -1.
Sample Input and Expected Output:
Input:
nums = [-1, 0, 3, 5, 9, 12]
target = 9
Output:
Index of target element 9: 4
Input:
nums = [-1, 0, 3, 5, 9, 12]
target = 2
Output:
Target element 2 not found in the sorted array.
Solution in C++:
We can solve the Binary Search problem using the iterative approach. We initialize two pointers, left and right, that define the search space. We calculate the mid index and compare the element at that index with the target. Depending on the comparison result, we either update left or right, effectively reducing the search space in half. We repeat this process until we find the target or exhaust the search space.
#include <iostream>
#include <vector>
int binarySearch(std::vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // Found the target element
} else if (nums[mid] < target) {
left = mid + 1; // Search the right half
} else {
right = mid - 1; // Search the left half
}
}
return -1; // Target element not found
}
int main() {
std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
int target1 = 9;
int target2 = 2;
int index1 = binarySearch(nums, target1);
int index2 = binarySearch(nums, target2);
if (index1 != -1) {
std::cout << "Index of target element " << target1 << ": " << index1 << std::endl;
} else {
std::cout << "Target element " << target1 << " not found in the sorted array." << std::endl;
}
if (index2 != -1) {
std::cout << "Index of target element " << target2 << ": " << index2 << std::endl;
} else {
std::cout << "Target element " << target2 << " not found in the sorted array." << std::endl;
}
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the Binary Search algorithm is O(log n), where n is the size of the nums array. This is because at each step, we reduce the search space by half.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array.