Q:

# C program to accept Sorted Array and do Search using Binary Search

Write a c program that will take input a sorted array and to binary search to find the element to be searched. (Output proper prompt messages in case element not found).

Algorithm:

Binary search actually divides the entire array into two halves at each iteration and do the search in one half based on the searching element since the array is sorted.

Let,

• Starting index=0
• End index=n-1, where n is the array length
• Middle index= (start + end index)/2= (n-1)/2, this middle index divides the array into two half
• If array[middle]==search value
• We are done
• Else if array [middle] < search value
• Then we need to search in the upper half
• Else if array [middle]>search value
• Then we need to search in the lower half
• These three cases need to be handled recursively to implement a binary search.
• Clearly, these searching method is possible due to the sorted input array.

Function definition:

We can build up a recursive binSearch()function which will do the binary search.

```Function binSearch(input array,start index, end index,search value)
middle index=(start index + end index)/2;
//if search value found return position(1-indexed position)
IF array[middle index] == search value
return middle index+1;
//if search value>array[middle index], search in the segment
//(middle index+1,end index), i.e., the upper half &
//search until start index==end index
ELSE IF (search value>array[middle index] &start index!= end index)
return binSearch(input array,middle index+1,end index,search value);//recursive call
//if search value<array [middle index] search in the segment
//(start index, middle index-1), i.e., the lower half& search until start index== end index
ELSE IF(search value<array[middle index] &start index!= end index)
return binSearch(input array, start index,middle index-1,seach value);
ELSE
return 0;
END Function```

Example & Explanation:

```    Let the input array be:
2 5 8 9 12 13 16, length, n=7
Search element: 5

//In main function:

Make call binSearch(array, 0,7,5)
binSearch (array, 0, 7, 5)
middle index =(0+7)/2=3
array!=5
array>5&& 0<7

make callbinSearch(array, 0, 3-1)
binSearch(array, 0, 3-1)
middle index =(0+2)/2=1
array==5
return (1+1) //position 2

Program terminated```

## C++ implementation for binary search on sorted array

``````#include <stdio.h>
#include <stdlib.h>

//binary search implementation using recursion
int binSearch(int* a,int first,int last,int t){
//find middle index
int mid=(first+last)/2;
//if data found return position(1-indexed position)
if(a[mid]==t)
return mid+1;
//if data > a[mid] search in the segment (mid+1,last)
else if(t>a[mid] & first!=last)//search until first!=last
return binSearch(a,mid+1,last,t);
//if data < a[mid] search in the segment (first,mid-1)
else if(t<a[mid] & first!=last)
return binSearch(a,first,mid-1,t);
else
return 0;
}

int main()
{
int n,t;
printf("enter number of array elements: ");
scanf("%d",&n);

int* a=(int*)(malloc(sizeof(int)*n));

printf("enter elements: \n");
//input array elements
for(int i=0;i<n;i++)
scanf("%d",&a[i]);

printf("enter element to search\n");
scanf("%d",&t);
//output result
if(binSearch(a,0,n-1,t))
printf("\n%d found at position %d\n",t,binSearch(a,0,n-1,t));
else

return 0;
}``````

Output (first run)

```enter number of array elements: 7
enter elements:
2 5 8 9 12 13 16
enter element to search
5

5 found at position 2
```

Output (second run)

```enter number of array elements: 6
enter elements:
11 34 45 56 67 78
enter element to search
20