Implement binary search on a sorted array using C programming language

Implement binary search on a sorted array using C programming language.

Code:

#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.

Explanation:

#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.

Binary Search Algorithm:

1. Input: Sorted array arr[], array size size, target value target.

2. Initialize two pointers left and right to the beginning and end of the array respectively.

3. Repeat the following steps while left is less than or equal to right:

   1. Calculate the middle index mid as (left + right) / 2.

   2. If the value at index mid is equal to the target value:

      • Return mid as the index where the target is found.

   3. 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.

   4. 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.

4. If the loop completes without finding the target, return -1 to indicate that the target is not present in the array.

Main Program Algorithm:

1. Initialize the sorted array arr[] with example values.

2. Calculate the size of the array by dividing the total size of the array by the size of a single element.

3. Set the target value that you want to search for.

4. Call the binarySearch function with the array, array size, and target value.

5. If the returned index from binarySearch is not -1:

   • Print a message indicating that the target element was found at the returned index.

6. If the returned index is -1:

   • Print a message indicating that the target element was not found in the array.

7. 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.

 

Time Complexity:

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.

 

Space Complexity:

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:

1. 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.

2. 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.

3. 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