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  to step  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

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$)

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 = {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);
}

return -1;
}

int main() {
// declare an array
int arr = {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);

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!