Binary search is a highly efficient algorithm for finding an element's position in a sorted array. Unlike linear search, which checks each element sequentially, binary search works by repeatedly dividing the search interval in half. This requires the array to be sorted beforehand.
low and high, which represent the bounds of the search area. Initially, low is set to the first index (0), and high is set to the last index (n - 1).mid = (low + high) / 2.high.low.low > high).Here’s a simple C++ implementation of binary search for a sorted array:
#include <iostream>
using namespace std;
// Function to perform binary search
int binarySearch(int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // Avoids potential overflow
if (arr[mid] == target) {
return mid; // Return the index if found
} else if (arr[mid] < target) {
low = mid + 1; // Search in the right half
} else {
high = mid - 1; // Search in the left half
}
}
return -1; // Return -1 if the target is not found
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11}; // Example sorted array
int size = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearch(arr, size, target);
if (result != -1) {
cout << "Element found at index: " << result << endl; // Output: Element found at index: 3
} else {
cout << "Element not found." << endl; // Output if not found
}
return 0;
}
binarySearch function takes a sorted array, its size, and the target value as parameters.low is set to 0 and high to the last index of the array.low is less than or equal to high.low + (high - low) / 2 helps avoid potential overflow.mid, its index is returned.high.low.binarySearch, and prints the result.Binary search is a powerful and efficient algorithm for searching in sorted arrays. Its logarithmic time complexity allows it to handle large datasets efficiently, making it a fundamental technique in computer science and programming. Always ensure that the array is sorted before applying binary search, as it relies on the order of elements for its functionality.
Open this section to load past papers