Write a program to perform Binary Search using C

 Binary search is a widely used searching algorithm that is efficient for finding a target value in a sorted array or list. It follows a divide-and-conquer approach by repeatedly dividing the search space in half until the target value is found or determined to be absent.

Here's how binary search works:

1. Start with a sorted array or list.
2. Set the lower bound (start) and upper bound (end) of the search space to the first and last elements of the array, respectively.
3. Calculate the middle index of the search space using the formula: mid = (start + end) / 2.
4. Compare the middle element with the target value:
   • If the middle element is equal to the target value, the search is successful, and the index is returned.
   • If the middle element is greater than the target value, the search space is reduced to the lower half of the array. Set the new upper bound (end) to mid - 1 and repeat step 3.
   • If the middle element is less than the target value, the search space is reduced to the upper half of the array. Set the new lower bound (start) to mid + 1 and repeat step 3.
5. Repeat steps 3 to 4 until the target value is found or the search space is empty (i.e., start becomes greater than end).
6. If the target value is not found, return a "not found" indication.

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This makes it very efficient compared to linear search, which has a time complexity of O(n) in the worst case. However, binary search requires the array to be sorted beforehand, which can add an additional overhead if the array is frequently modified.

Algorithm 

def binary_search(arr, target):
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            start = mid + 1
        else:
            end = mid - 1

    return -1  # Target value not found


# Example usage:
array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_value = 23

result = binary_search(array, target_value)

if result != -1:
    print(f"Target value {target_value} found at index {result}.")
else:
    print("Target value not found in the array.")

Program 

/* Program to Search an Element using BInary Search */

#include 
/* Function Prototype Declaration */
void binary_search();

/* Global Declaration of Variables */
int a[50], n, item, loc, beg, mid, end, i;

/* We used main() because it's a C-Compiler.
   Use void main() or int main() if necessary  */

main()
{
    printf("\nEnter size of an array: ");
    scanf("%d", &n); // Reading Size of an Array.

    printf("\nEnter elements of an array in sorted form:\n");
    for(i=0; i<n; i++)
        scanf("%d", &a[i]);  //Read Array values one by one.

    printf("\nEnter ITEM to be searched: ");
    scanf("%d", &item);

    /* Calling Function - No Arguments Passing */
    binary_search();    
}
void binary_search()  //called Function - Dont Return Anything.
{
    /* Binary Search Logic */
    
    beg = 0;
    end = n-1;
    mid = (beg + end) / 2;
    while ((beg&lt=end) && (a[mid]!=item))
    {
        if (item &lt a[mid])
            end = mid - 1;
        else
            beg = mid + 1;
        mid = (beg + end) / 2;
    }
    if (a[mid] == item)
        printf("\n\nITEM found at location %d", mid+1);
    else
        printf("\n\nITEM doesn't exist");
}


Output:

Enter size of an array: 6

Enter elements of an array in sorted form:
10 20 30 40 50 60

Enter ITEM to be searched: 30


ITEM found at location 3