# Binary Search

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

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:

1. Iterative Method
2. 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);
int x = 3;
int result = binarysearch(data, x, 0, n-1);
if(result == -1)
else
printf("Elements is found");
return 0;
```Code language: C++ (cpp)```
``````Output:
Element is found``````

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

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

### Applications

1. Number guessing game
2. Word lists/ search dictionary etc

### Linear Search

Here, We discuss about Linear Search, their implementation in C, time and space complexity and its applications. What is Linear Search? Linear Search is the simplest …

### 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. 