# Binary Search in C

## Binary Search in C

Binary search is a very fast and efficient searching algorithm. It requires to be list be in sorted order, ie; either in ascending or descending.

Lets have a look at binary search below –

 Time Complexity (Best) Ω(1) Time Complexity (Avg) Θ(log n) Time Complexity (Worst) O(log n) Space Complexity O(1)

## How Binary Search in C works?

1. The array needs to be sorted in either ascending or descending order
2. In our case we are taking an example for an array sorted in ascending order.
3. The searching algorithm proceed from any of two halves
4. Depends upon whether the element you are searching is greater or smaller than the central element
5. If the element is small then, searching is done in first half
6. If it is big then searching is done in second half.

It is fast search algorithm with the complexity of O(log n).

## Implementation of Binary Search

• Take a sorted array (mandatory)
• Find mid using formula m = (l+r)/2
• If the item to be searched is greater than mid
• Check the right subarray
• If the item to be searched is lesser than the mid
• Check the left subarray
• If mid element == item return with the position where found
• Else keep doing the above steps until you violate the bounds of the array

## Methods Discussed

We are going to be discussing two methods here –

• Method 1: Recursive Approach
• Method 2: Iterative Approach

## Binary Search in C (Recursive Approach)

Note – This method uses recursion in C.

Run
```// Binary Search implimentation in C (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include <stdio.h>

int binarySearch(int arr[], int left, int right, int item){

if (right >= left){

// calculation of new mid
int mid = left + (right - left)/2;

// returns position where found
if (arr[mid] == item)
return mid;

// goes to recursive calls in left half
if (arr[mid] > item)
return binarySearch(arr, left, mid-1, item);

// goes to recursive calls in right half
else
return binarySearch(arr, mid+1, right, item);
}
else
return -1;
}
int main(){
// array needs to be sorted to impliment binary search
int arr[8] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 70;

int position = binarySearch(arr, 0, n-1, item);

if(position == -1)
else
printf("%d Found at index : %d",item, position);
}```

### Output:-

```70 Found at index : 6
```

## Binary Search in C (Iterative Approach)

Let’s look at this approach below

Run
```// Binary Search implimentation in C (Iterative)
// Time Complexity : O(N)
// Space Complexity : O(1)
#include <stdio.h>

// Returns index of item in given array, if it is present
// otherwise returns -1
int binarySearch(int arr[], int l, int r, int item)
{
while (l <= r) {
int mid = l + (r - l) / 2;

// if item is at mid
if (arr[mid] == item)
return mid;

// If item greater, ignore left half, consider only right half
if (arr[mid] < item)
l = mid + 1;

// If item is smaller, ignore right half, consider only left half
else
r = mid - 1;
}

// if we are able to reach here
// means item wasn't present
return -1;
}

int main(void)
{
// array needs to be sorted to impliment binary search
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 30;

int position = binarySearch(arr, 0, n - 1, item);

if(position == -1)
else
printf("%d Found at index : %d",item, position);

return 0;
}```

### Output

`30 Found at index : 2`

O(1)

O(log n)

O(log n)

O(1)

## Average Comparisions

Log(N+1)

### Quiz Time

Question 1.Binary search algorithm can’t be applied to

1. Pointed Array List
2. Sorted Binary Tree
3. Unordered Array

(Cisco, Walmart Labs)

You cannot use a binary search on an unsorted list. Your best bet is to probably iterate over the list’s items until you find the element you are looking for, an O(n) operation, i.e. do linear search

Ans. C

Question 2. Which is the following searching algorithms works on the divide and conquer?

1. Binary Search
2. Linear
3. Sequential
4. Merge Sort

(CoCubes, Atos Syntel)

Binary search only checks the middle element of the array. when it checks the middle element and middle element is not equal to the given element then we divide the list in two subparts.

Ans: Both A & D

## Searching

Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.