Binary search in C programming

Binary search is a search method used in programming language which use divide and rule logic.
Suppose there are 10 elements in an array and the rule of binary search is the array must be pre-sorted. So here is the list of elements in the array.





array elements - 3   4   6   8  12   16   18  24   39  44
array index      - 0   1   2   3    4     5    6   7      8     9

So there are 10 elements 0-9. Now in binary search we need to divide the array into 2 half taking the middle element and checking whether the element is greater / lesser or equal to the search key. If it is greater than the search key then the search key should be on the right half of the array therefore we can discard the left half and set the mid element as the lower bound of the array, if it is lesser than the search key then the search key should be on the left half of the array therefore we can discard the right half. Now we repeat this task by again and gain dividing the array and taking the mid element and comparing it with the search key.

Now let us test with the above array elements. Let our search key be 18.

1.

array elements - 3   4   6   8  12   16   18  24   39  44
array index      - 0   1   2   3    4     5    6   7      8     9

Mid element is (9+0)/2 = 4 which is 12.

12<18, therefore we can set lower bound of the array as 4+1 = 5 and discard 0 to 4.

2. 
array elements - 16   18  24   39  44
array index      -  5     6    7     8     9

Now  Mid element is (9+5)/2 = 7 which is24.

24>18, therefore we can set upper bound of the array as 7-1 = 6 and discard8 and 9.

3.
array elements - 16   18  24
array index      -  5     6    7 

Now  Mid element is (7+5)/2 = 6 which is18

18=18, therefore this is our search element. So we found the result.

4. 
Now suppose search key does not exists, in that case lower bound will be greater than upper bound and the loop terminates, displaying a message as search element not found.

Here is a C program on Binary search. Please go through the program.

Now  Mid element is (9+5)/2 = 7 which is24.

24>18, therefore we can set upper bound of the array as 7-1 = 6 and discard8 and 9.


#include<stdio.h>

void main()
{

//Array is pre-initiated to save time, we are not concern about user input or sorting of array here.

int arr[]={5,8,9,13,17,23,29,34,39,45,49,54,59,62,79,81,84,88,93,96,99,102};

int num; // num variable is declared for search  key input from user.

int low,high,mid,flag; // low, high and mid variable are lower bound, upper bound and mid element.

printf("\nEnter number to search : ");

scanf("%d",&num); //User enters the search key.

low=0; //lower bound is initially set to 0

high=21; // Upper bound is initially set to actual upper bound of the array

mid=(low+high)/2; //mid position is set.

while(low<=high) // This condition is important, checking goes on until low<=high

{

    if(num<arr[mid]) // if search key less than mid element

    high=mid-1; // set upper bound to one element left to mid element

    else if(num>arr[mid]) // if search key greater than mid element

        low=mid+1; // set lower bound to one element right to mid element

    else
    {

        break; //else search key matches mid element so exit the loop.

    }

    mid=(low+high)/2; // this process goes on after setting lower / upper bound

}

/* check if low<=high then the loop is terminated because mid element matched
search key*/
if(low<=high)  

    printf("%d found in %d position",num,mid); // print the search key and position where it is found.

}


#clanguage #cprogramming #programminginc #binarysearch