C Program To Implement Binary Search

Binary search is used to find the position of a given value within a sorted array.  It is faster than linear search.  It works by searching the given value with the middle element of the sorted array.  If the search value is the middle element, then we found the position of the search element.  If search value is less than the value of middle element, then the search value should be present at the left sub-array. Repeat the above steps until we find the search element.

Example:
Search 10 from the below data
50   10   20   40   30

Sort the given data:
10   20   30   40   50

Apply Binary Search Algorithm:
low = 0  and high = 4
middle = (0 + 4) / 2 = 2

Element at index 2 is the middle element (30)
10   20         30         40   50

Search value is 10
10 < 30

So, ignore right sub-array
10   20
middle = (0 + 1) / 2 = 0

Element at index 0 is our search element.  So, search element is present in our sorted list and its index is 0.

See Also:
C Program To Implement Binary Search
C Program To Implement Linear Search On Sorted & Unsorted Array
C Program To Implement Brute Force Algorithm
C program To Implement Knuth-Morris-Pratt Algorithm

Example Program For Binary Search(in C):

---

  #include <stdio.h>
  #include <stdlib.h>
  void sort(int *data, int n) {
        int i, j, temp;
        for (i = 1; i < n; i++) {
                temp = data[i];
                for (j = i; j > 0 && data[j-1] > temp; j--) {
                        data[j] = data[j-1];
                }
                data[j] = temp;
        }
  }

  int main() {
        int i, high, low, mid, n, *data, element, ch = 1;
        printf("Binary Search Example:\n");
        printf("Enter the number of entries:");
        scanf("%d", &n);
        data = (int *)malloc(sizeof (int) * n);
        for (i = 0; i < n; i++) {
                scanf("%d", &data[i]);
        }
        sort(data, n);
        printf("After sorting:");
        for (i = 0; i < n; i++)
                printf("%3d ", data[i]);
        printf("\n");
        while (ch) {
                printf("Enter the data to be searched:");
                scanf("%d", &element);
                low = 0, high = n-1;
                while (low <= high) {
                        mid = (high + low) / 2;
                        if (data[mid] < element)
                                low = mid + 1;
                        else if (data[mid] > element)
                                high = mid - 1;
                        else {

                                printf("Search element %d found "

                                        "at index %d\n", element, mid);

                                break;

                        }

                }

                printf("Searched element is not available\n");

                printf("Do you wanna continue search(1/0):");

                scanf("%d", &ch);

        }

        return 0;

  }

  Output: (C Program To Implement Binary Search)

  jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out
  Binary Search Example:
  Enter the number of entries:5
  50   10   20   40   30
  After sorting: 10  20  30  40  50 
  Enter the data to be searched:10
  Search element 10 found at index 0
  Searched element is not available
  Do you wanna continue search(1/0):1
  Enter the data to be searched:20
  Search element 20 found at index 1
  Searched element is not available
  Do you wanna continue search(1/0):1
  Enter the data to be searched:30
  Search element 30 found at index 2
  Searched element is not available
  Do you wanna continue search(1/0):0