search sorted array c

Searching a Sorted Array in C

To search for an element in a sorted array in C, you can use the binary search algorithm. Here are the steps involved in performing a binary search on a sorted array:

1. Initialize variables: Start by initializing two variables, low and high, to represent the lower and upper bounds of the search range. Set low to the index of the first element in the array (0) and high to the index of the last element in the array (array_length - 1).

2. Search for the target element: Repeat the following steps until low is less than or equal to high:

3. Calculate the middle index of the current search range by taking the average of low and high: mid = (low + high) / 2.

4. Compare the target element with the element at the middle index:

   • If the target element is equal to the middle element, return the middle index as the position of the target element.
   • If the target element is less than the middle element, update high to mid - 1 to search in the lower half of the array.
   • If the target element is greater than the middle element, update low to mid + 1 to search in the upper half of the array.

5. Handle the case when the target element is not found: If the loop terminates without finding the target element, it means the element is not present in the array. You can return a special value (e.g., -1) to indicate that the element was not found.

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

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid; // Element found at index mid
        } else if (arr[mid] < target) {
            low = mid + 1; // Search in the upper half
        } else {
            high = mid - 1; // Search in the lower half
        }
    }

    return -1; // Element not found
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binarySearch(arr, n, target);

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

    return 0;
}

In this example, the binarySearch function takes an array arr, the size of the array n, and the target element target as parameters. It returns the index of the target element if found, or -1 if not found. The main function demonstrates how to use the binarySearch function to search for the element 7 in the sorted array arr.

I hope this explanation helps! Let me know if you have any further questions.