// Binary search in an int array
int binary_search(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
// Divide and rule
if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
// Element not found in the array
return -1;
}
Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half, comparing the target value to the middle element of the interval, and then determining which half to search based on whether the target value is less than or greater than the middle element. This process continues until the target value is found or the search interval is empty, indicating that the target value is not present in the array.
The "Divide and Rule" strategy, also known as "Divide and Conquer," is a fundamental algorithmic technique used to solve complex problems by breaking them down into simpler sub-problems. This approach involves dividing the problem into smaller, more manageable parts, solving each part independently, and then combining the solutions to form the final result. In the context of binary search, this method is employed by repeatedly dividing the search interval in half until the target value is found or the interval is empty. This technique is efficient for problems where the solution can be constructed from solutions to smaller instances of the same problem.
The time complexity of the binary search algorithm is O(log n), where n is the number of elements in the array. This logarithmic complexity arises because each iteration of the binary search halves the search space, significantly reducing the number of comparisons needed to find the target value. As a result, binary search is highly efficient compared to linear search algorithms, especially for large datasets. The space complexity of binary search is O(1) in its iterative form, as it only requires a constant amount of additional memory for variables, regardless of the size of the input array.