Last updated on September 4th, 2023 at 09:41 pm

Here, We discuss about Binary Search, their implementation in C, time and space complexity and its applications.

**What is Binary Search?**

**Binary Search** is the most popular searching algorithm. It is efficient and most commonly used to solve problems.

The algorithm based on the idea that finding an element’s position in a sorted array.

Binary search works only on a sorted array. To use binary search, the array must be sorted first.

Binary Search Algorithm can be implemented in two ways are:

- Iterative Method
- Recursive Method

**Implementation**

**Sample Code in C:**

```
//Binary Search in C
#include<stdio.h>
int binarysearch(int arr[], int x, int low, int high)
{
//repeat until the pointers low and high meet each other
while(low <= high)
{
int mid = low + (high-low)/2;
if(arr[mid] == x)
return mid;
if(arr[mid] < x)
return mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void)
{
int data[] = {3, 15, 8, 1, 38, -2, 7};
int n = sizeof(data) / sizeof(data[0]);
int x = 3;
int result = binarysearch(data, x, 0, n-1);
if(result == -1)
printf("Element not found");
else
printf("Elements is found");
return 0;
```

Code language: C++ (cpp)

```
Output:
Element is found
```

**Advantages**

- Efficient on very big list.
- Can be implemented iteratively/recursively.

**Disadvantages**

- Interacts poorly with the memory hierarchy (more cache miss).
- Requires given list to be sorted.
- Due to random access of list element, needs arrays instead of linked list.

**Time and Space Complexity**

Time Complexity | |

Worst Case | O(log n) |

Best Case | O(1) |

Average Case | O(log n) |

Space Complexity | |

Worst Case | O(n) |

**Applications**

- Number guessing game
- Word lists/ search dictionary etc

### Related:

#### Linear Search

Here, We discuss about Linear Search, their implementation in C, time and space complexity and…

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to ðŸ“§ **[email protected]**. See your articles on the main page and help other coders.ðŸ˜Ž