Introduction
Binary search is an efficient algorithm for finding a specific value in a sorted array. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half; otherwise, it continues in the upper half. This method drastically reduces the number of comparisons needed to find the target value, making it much faster than linear search for large datasets.
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if the target is present at mid
if (arr[mid] == target) {
return mid; // Return the index if found
}
// If target is greater, ignore the left half
else if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore the right half
else {
right = mid - 1;
}
}
return -1; // Return -1 if not found
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int size = sizeof(arr) / sizeof(arr[0]);
int target;
printf("Enter the number to search: ");
scanf("%d", &target);
int result = binarySearch(arr, size, target);
if (result != -1) {
printf("Element found at index: %d\n", result);
} else {
printf("Element not found in the array.\n");
}
return 0;
}
Explanation
- Function Definition:
binarySearch(int arr[], int size, int target)
: Takes a sorted array, its size, and the target value to search for.
- Initialization:
- Two pointers,
left
andright
, are initialized to the start and end of the array, respectively.
- Two pointers,
- Loop:
- A
while
loop runs as long asleft
is less than or equal toright
. - The middle index (
mid
) is calculated, and the target is compared with the value atmid
. - Depending on the comparison:
- If the target equals
arr[mid]
, the index is returned. - If the target is greater,
left
is updated tomid + 1
. - If the target is smaller,
right
is updated tomid - 1
.
- If the target equals
- A
- Return Values:
- Returns the index of the target if found.
- Returns -1 if the target is not found.
- Main Function:
- Initializes a sorted array and prompts user input for the target value.
- Calls
binarySearch
and displays the result.
Input
When you run the program, it prompts the user to enter a number to search for. For example:
Enter the number to search: 7
Output
The output will indicate whether the element was found and, if so, at which index:
Element found at index: 3
Or if the element is not found:
Element not found in the array.
Conclusion
Binary search is a highly efficient algorithm for searching elements in a sorted array, with a time complexity of O(log n). This makes it significantly faster than linear search, especially for larger datasets. However, it is crucial that the array is sorted before applying binary search. Its effectiveness and efficiency make it a popular choice in many applications where fast search operations are required.