#include <stdio.h>
// Binary Search function
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 the middle
if (arr[mid] == target)
return mid;
// If the target is greater, ignore the left half
if (arr[mid] < target)
left = mid + 1;
// If the target is smaller, ignore the right half
else
right = mid - 1;
}
// Target is not present in the array
return -1;
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 12;
int result = binarySearch(arr, size, target);
if (result != -1)
printf("Element %d found at index %d\n", target, result);
else
printf("Element %d not found in the array\n", target);
return 0;
}
In this example, the binarySearch
function takes the sorted array, its size, and the target element as inputs and returns the index where the target is found or -1 if the target is not present in the array. The main
function demonstrates how to use the binarySearch
function by searching for the element 12 in the given sorted array.
Remember that binary search requires the array to be sorted. The algorithm works by repeatedly dividing the search interval in half and comparing the middle element of the interval to the target value. Based on the comparison, it eliminates half of the search interval and continues the search until the target is found or the interval becomes empty.
#include <stdio.h>
This line includes the standard input-output library, which provides functions for input and output operations.
int binarySearch(int arr[], int size, int target) {
This is the start of the function called binarySearch
. It takes three inputs: an array arr
, an integer size
representing the size of the array, and an integer target
representing the value we're searching for. It will return an integer that represents the index of the target value in the array.
int left = 0;
int right = size - 1;
Two variables left
and right
are initialized. These will be used to keep track of the range of elements within which the target value might exist. At the start, left
is set to the first index (0) and right
is set to the last index of the array.
while (left <= right) {
This initiates a loop that continues as long as the left
index is less than or equal to the right
index. This means there are still elements within the search range.
int mid = left + (right - left) / 2;
This calculates the middle index, mid
, of the current search range. It's done by taking the average of left
and right
, which helps to divide the search interval in half.
if (arr[mid] == target)
return mid;
This checks if the value at the middle index (arr[mid]
) is equal to the target value we're looking for. If they are equal, it means we found the target value, so the function returns the index mid
.
if (arr[mid] < target)
left = mid + 1;
If the value at the middle index is less than the target value, it means the target must be on the right side of the middle. So, left
is updated to mid + 1
, moving the search range to the right half of the array.
else
right = mid - 1;
If the value at the middle index is greater than the target value, it means the target must be on the left side of the middle. So, right
is updated to mid - 1
, moving the search range to the left half of the array.
This is the end of the while
loop. The loop continues until the search range (left
to right
) becomes empty, meaning the target value is not in the array.
return -1;
If the loop completes without finding the target value, the function returns -1 to indicate that the target value is not present in the array.
}
int main() {
This is the beginning of the main
function, which is the entry point of the program.
int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
An example array is created with sorted values.
int size = sizeof(arr) / sizeof(arr[0]);
The size of the array is calculated by dividing the total size of the array by the size of a single element in the array.
int target = 12;
The value we're searching for is set to 12.
int result = binarySearch(arr, size, target);
The binarySearch
function is called with the array, its size, and the target value. The returned index (or -1 if not found) is stored in the variable result
.
if (result != -1)
printf("Element %d found at index %d\n", target, result);
else
printf("Element %d not found in the array\n", target);
Depending on whether the result
is -1 or not, this code prints whether the target element was found in the array or not.
return 0;
}
The main
function returns 0 to indicate successful completion of the program.
Binary Search Algorithm:
Input: Sorted array arr[]
, array size size
, target value target
.
Initialize two pointers left
and right
to the beginning and end of the array respectively.
Repeat the following steps while left
is less than or equal to right
:
Calculate the middle index mid
as (left + right) / 2
.
If the value at index mid
is equal to the target
value:
Return mid
as the index where the target
is found.
If the value at index mid
is less than the target
value:
Update left
to mid + 1
to search in the right half of the array.
If the value at index mid
is greater than the target
value:
Update right
to mid - 1
to search in the left half of the array.
If the loop completes without finding the target
, return -1
to indicate that the target
is not present in the array.
Main Program Algorithm:
Initialize the sorted array arr[]
with example values.
Calculate the size of the array by dividing the total size of the array by the size of a single element.
Set the target
value that you want to search for.
Call the binarySearch
function with the array, array size, and target value.
If the returned index from binarySearch
is not -1
:
Print a message indicating that the target
element was found at the returned index.
If the returned index is -1
:
Print a message indicating that the target
element was not found in the array.
End the program by returning 0
.
This algorithm demonstrates how binary search works by repeatedly dividing the search interval in half and narrowing down the search range until the target element is found or the search range becomes empty. It's an efficient algorithm for searching in sorted arrays as it eliminates half of the remaining search space with each comparison.
The time complexity of the binary search algorithm, as implemented in the above C program, is O(log N), where N is the number of elements in the sorted array.
Here's why:
In each iteration of the binary search loop, the search range is effectively halved. This means that after the first iteration, the search range becomes approximately N/2 elements, then N/4 elements after the second iteration, N/8 after the third, and so on. The number of iterations required to reduce the search range to 1 element is log₂(N).
Each iteration involves a constant amount of work: comparing the middle element to the target value and updating the left and right pointers. Therefore, the number of iterations (log₂(N)) dominates the overall time complexity.
Since the number of iterations needed is proportional to the logarithm of the input size (N), the time complexity of binary search is O(log N). This logarithmic time complexity makes binary search very efficient for large arrays compared to linear search algorithms that have a time complexity of O(N), where the number of operations grows linearly with the input size.
The space complexity of the above C program for binary search is O(1), which means that the amount of memory used by the program doesn't grow with the size of the input array.
Here's why:
Input Data: The input data (sorted array, array size, and target value) doesn't require additional space that scales with the size of the input. These inputs are directly passed to the functions and are not stored in any data structure that grows with the input size.
Variables: The program uses a few integer variables such as left
, right
, mid
, size
, target
, and result
to keep track of indices and values during the execution of the algorithm. These variables require a constant amount of memory regardless of the size of the input array.
Function Call Stack: The program doesn't involve any recursive function calls or dynamic memory allocations that would create a growing call stack or heap memory usage. The binary search algorithm is implemented using a simple loop, so there are no stack frames being added for each recursive call.
Overall, the program's memory usage remains constant regardless of the input size. Therefore, the space complexity of the program is O(1), indicating a constant amount of space usage.
Thank You