## Binary Search

### Binary search in C programming

As we have learned linear search takes too long for long size array. So there is another search called **binary search**.

#### The objective of binary Search

Search an element item in an array arr[0...n-1] using binary search. If element found then return the position otherwise return -1.

#### The requirement for binary search

For binary search, it is required that the given array should be sorted in ascending order.

#### Basic Concept of binary search

In binary search to search an element item, each element is not matched. To perform the binary search the following process is followed...

- As we know that an array is a bounded structure that has two boundaries lower bound and upper bound.
- Lower bound of the array is
and if the array size is represented by n then the upper bound of the array is*0*. so we take two-variable lb and ub and initialized with a lower bound and upper bound respectively. The following code initializes the value of lb and ub.*n-1* **lb = 0; ub = n - 1;**- After initializing lower bound and upper bound we find the mid index by calculating the mid-position by using the following formula.
**mid = (lb + ub) / 2;**- After finding the mid-position we match the item with the arr[mid], if match found the return the mid otherwise two cases are possible either the item is greater than mid or lower than mid.
- If the item is greater than mid we set the
**lb**toand repeat the process again. In this way, we reject the half part array of that is lower than mid position.*mid + 1* - If the item is smaller than mid we set the
to*ub*and repeat the process again. In this way, we reject the half part of the array that is higher than mid position.*mid - 1* - We repeat this process until
because continues we break the array in half. For example, if initially array size is 10 then in the next iteration it will be 5 followed by 2 and 1. When array size is 1 then lb and up becomes the same means this will be the last element to test. if it is also doesn't match then the item not found in the array.*lb <= ub* - Let's go through the following program to understand the concept.

### Program to find an element item in an array using binary search.

#include<stdio.h> int binary_search(int arr[],int n,int item) { int lb = 0; int ub = n - 1; int mid; while(lb <= ub) { mid = (lb + ub) / 2; if(item == arr[mid]) { return mid; } else if(item > arr[mid]) { lb = mid + 1; } else { ub = mid - 1; } } return -1; } int main() { int arr[20]; int i,n; int item,pos; printf("Enter how many element, (max:20): "); scanf("%d",&n); //Array input for(i = 0; i < n; i++) { printf("Enter element %d: ",i+1); scanf("%d",&arr[i]); } //Item to search printf("Enter the item to search: "); scanf("%d",&item); pos = binary_search(arr,n,item); if(pos != -1) { printf("Item found at index %d",pos); }else { printf("Item not found"); } return 0; }

#### Output

Enter how many element, (max:20): 5 Enter element 1: 10 Enter element 2: 20 Enter element 3: 30 Enter element 4: 40 Enter element 5: 50 Enter the item to search: 30 Item found at index 2

Enter how many element, (max:20): 5 Enter element 1: 10 Enter element 2: 20 Enter element 3: 30 Enter element 4: 40 Enter element 5: 50 Enter the item to search: 25 Item not found