Binary search is an efficient searching algorithm for sorted data structures. It works by repeatedly dividing the search interval in half and comparing the target value with the iddle element. Based on the comparison, the search interval is further reduced to the left or right half until the target is found or the interval becomes empty.

Here's an explanation of the binary search algorithm:

1. Start with a sorted data structure (e.g., an array).

2. Set the left pointer to the start of the structure and the right pointer to the end.

3. Repeat until the left pointer is less than or equal to the right pointer: a. Set the middle pointer as the floor value of the average of the left and right pointers.
b. Compare the target value with the element at the middle pointer.
c. If the target is found, return the index of the middle element.
d. If the target is less than the middle element, update the right pointer to be one position before the middle element.
e. If the target is greater than the middle element, update the left pointer to be one position after the middle element.

4. If the target is not found, return a value indicating that the target does not exist in the data structure.

Here's an example implementation of binary search in C:

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2; // Calculate the middle index

        if (arr[mid] == target) {
            return mid; // Target found at index mid
        } else if (arr[mid] < target) {
            left = mid + 1; // Update left pointer
        } else {
            right = mid - 1; // Update right pointer
        }
    }

    return -1; // Target not found
}

int main() {
    int arr[] = {4, 8, 15, 16, 23, 42};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 16;

    int result = binarySearch(arr, 0, size - 1, target);

    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

In this example, the `binarySearch` function performs the binary search algorithm on the given array. It takes the array, the left and right indices of the search interval, and the target value as inputs. The function iteratively divides the search interval and compares the target with the middle element. If the target is found, the function returns the index of the element. If the target is less than the middle element, the right pointer is updated. If the target is greater than the middle element, the left pointer is updated. If the target is not found after the search interval is empty (left > right), the function returns -1. In the `main` function, we create a sorted array, specify the target value, and call the `binarySearch` function to search for the target. The result is then printed based on whether the target was found or not.

The output will be:

Element found at index 3

As you can see, the binary search algorithm successfully finds the target element at index 3 in the given sorted array.

Time Complexity

The time complexity of binary search in the context of design and analysis of algorithms (DAA) is typically represented using Big O notation.

Binary search is a searching algorithm that works efficiently on sorted arrays or lists by repeatedly dividing the search interval in half. The basic idea is to compare the target value with the middle element of the array, and based on the comparison, narrow down the search range to either the lower or upper half of the array. By iteratively performing this process, the algorithm eventually either finds the target element or determines that it does not exist in the array.

The time complexity of binary search is O(log n), where n represents the number of elements in the array. This logarithmic time complexity arises from the fact that with each comparison, the search range is halved. As a result, the algorithm quickly converges towards the target value.

In terms of DAA, the time complexity of O(log n) for binary search indicates that the algorithm scales efficiently as the size of the input increases. It is significantly faster than linear search algorithms, which have a time complexity of O(n). However, it is important to note that binary search requires a sorted array as input, and the process of sorting the array itself may have a higher time complexity depending on the sorting algorithm used.

Space Complexity

The space complexity of binary search in the context of design and analysis of algorithms (DAA) is O(1), which is constant space.

Binary search is an iterative algorithm that does not require any additional data structures or dynamic memory allocation. It uses a few variables to keep track of the search range, such as the indices for the start and end points of the current interval. These variables require a constant amount of space, regardless of the size of the input array.

In terms of space complexity analysis, the space usage remains constant as the size of the input increases. Therefore, the space complexity of binary search is O(1). This means that the algorithm uses a fixed amount of memory, independent of the input size, making it space-efficient.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc