Home / C / Searching / C Program for Binary Search

C Program for Binary Search

in ,
Search

C program for binary search has been shown here. Both the iterative and recursive methods have been shown below. Binary search works only in a sorted array. The following section also covers the algorithm, pseudocode and time complexity of the program.







1. Take input of an array A[] and the search element m

2. Set the left most index l = 0 and the right most index as r = size(A) - 1

3. Repeat from steps [4] to step [10] until r >= l

4. Compute the middle index mid = l + (r - l)/2

5. Check if arr[mid] == m

6. If step 5 is true, display the position mid + 1 as output and exit the program.

7. Check if arr[mid] > m

8. If step 7 is true, display the position set r = mid - 1

9. Check if arr[mid] < m

10. If step 9 is true, display the position set l = mid + 1

11. If element was not found, display "Not found"!






Input: An array $A[~]$, left index $l$, right index $r$ and search element $m$

Output: Position of $m$ in $A[~]$

1. Procedure binarySearch($A[~]$, $l$, $r$, $m$):

2. If $r \geq l$:

3. $mid \leftarrow l + (r - l) / 2$:

4. If $A[mid] == m$:

5. Return $mid$

6. If $A[mid] > m$:

7. Return binarySearch($A[~]$, $l$, $mid - 1$, $m$)

8. Return binarySearch($A[~]$, $mid + 1$, $r$, $m$)

9. Return "Element not found"

10. End Procedure






Time Complexity: O(log(n))

Where n is the total no of elements in the array.





4. C Program for binary search using iteration

Code has been copied
/******************************************
        alphabetacoder.com
C program for binary search using iteration
********************************************/

#include <stdio.h>

int main() {
    // declare an array
    int arr[10] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};

    // declare variables
    int i, m, l, r, mid, flag = 0, position;

    // take input from user to search element
    printf("Enter the element to search: ");
    scanf("%d", & m);

    // initialize leftmost and rightmost index
    // array of length has index range 0 to 9
    l = 0;
    r = 9;

    // keep checking middle position until right index >= left index
    while (r >= l) {
        mid = l + (r - l) / 2;

        // if element is at middle then stop the search
        // set flag = 1 as element has been found
        if (arr[mid] == m) {
            flag = 1;
            break;
        }

        // if element is smaller than arr[mid],
        // set r = mid - 1 i.e. ignore right subarray of mid
        if (arr[mid] > m)
            r = mid - 1;

        // if element is bigger than arr[mid],
        // set l = mid + 1 i.e. ignore left subarray of mid
        if (arr[mid] < m)
            l = mid + 1;
    }

    // check if element has been found
    if (flag == 1)
        printf("%d has been found at position %d ", m, mid + 1);
    else
        printf("%d can not be found!", m);

    return 0;
}

Output

Case 1:

Enter the element to search: 35

35 has been found at position 7


Case 2:

Enter the element to search: 23

23 can not be found!




5. C Program for binary search using recursion

Code has been copied
/*******************************************
        alphabetacoder.com
C program for binary search using recursion
********************************************/

#include <stdio.h>

// recursive function to perform binary search
// arr[] is the array
// l is the index of leftmost element of search range
// r is the index of rightmost element of search range
// m is the search element
int binarySearch(int arr[], int l, int r, int m) {
    // compute mid index until right index >= left index
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // if element is at middle then return mid
        if (arr[mid] == m)
            return mid;

        // if element is smaller than arr[mid]
        //search the left subarray of mid i.e.
        // left index to mid - 1
        if (arr[mid] > m)
            return binarySearch(arr, l, mid - 1, m);

        // Element is smaller than arr[mid]
        //search the right subarray of mid i.e.
        // mid + 1 index to right index
        return binarySearch(arr, mid + 1, r, m);
    }

    // element was not found, so return -1
    return -1;
}

int main() {
    // declare an array
    int arr[10] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};

    // declare variables
    int i, m, position;

    // take input from user to search element
    printf("Enter the element to search: ");
    scanf("%d", & m);

    // call function to search element
    // arr is the array
    // 0 is the leftmost index
    // 9 is the right most index
    position = binarySearch(arr, 0, 9, m);

    // check if not found
    if (position == -1)
        printf("%d can not be found!", m);
    else
        printf("%d has been found at position %d ", m, position + 1);

    return 0;
}

Output

Case 1:

Enter the element to search: 35

35 has been found at position 7


Case 2:

Enter the element to search: 23

23 can not be found!




Labels: ,