**Binary Search Algorithm**

Search as the name suggests, is an operation of finding an item from the given collection of items. Binary Search algorithm is used to find the position of a specified value (an ‘Input Key’) given by the user in a sorted list.

**Algorithm:**

It starts with the middle element of the list.

1. If the middle element of the list is equal to the ‘input key’ then we have found the position the specified value.

2. Else if the ‘input key’ is greater than the middle element then the ‘input key’ has to be present in the last half of the list.

3. Or if the ‘input key’ is lesser than the middle element then the ‘input key’ has to be present in the first half of the list.

Hence, the search list gets reduced by half after each iteration.

First, the list has to be sorted in non-decreasing order.

[low, high] denotes the range in which element has to be present and [mid] denotes the middle element. Initially low = 0, high = number_of_elements and mid = floor((low+high)/2). In every iteration we reduce the range by doing the following until low is less than or equal to high(meaning elements are left in the array) or the position of the ‘input key’ has been found.

(i) If the middle element (mid) is less than key then key has to present in range [mid+1 , high], so low=mid+1, high remains unchanged and mid is adjusted accordingly

(ii) If middle element is the key, then we are done.

(iii) If the middle element is greater than key then key has to be present in the range [low,mid-1], so high=mid-1, low remains unchanged and mid is adjusted accordingly.

**Properties:**

1. Best Case performance – The middle element is equal to the ‘input key’ O(1).

2. Worst Case performance - The ‘input key’ is not present in the list O(logn).

3. Average Case performance – The ‘input key’ is present, but it’s not the middle element

O(logn).

4. The List should be sorted for using Binary Search Algorithm.

5. It is faster than Linear Search algorithm, and its performance increases in comaparison to

linear search as N grows.

**Complete tutorial with an example :**

## Binary Search - C Program Source Code

#include<stdio.h>

/* Logic: [low, high] denotes the range in which element has to be present.

Initially low = 0, high = number_of_elements which covers entire range.

In every step we reduce the range by doing the following

(i) If the middle element (mid) is less than key then key has to present in range [mid+1 , high]

(ii) If middle element is the key, then we are done.

(iii) If the middle element is greater than key then key has to be present in the range[low,mid-1]

*/

int BinarySearch(int *array, int number_of_elements, int key)

{

int low = 0, high = number_of_elements-1, mid;

while(low <= high)

{

mid = (low + high)/2;

if(array[mid] < key)

{

low = mid + 1;

}

else if(array[mid] == key)

{

return mid;

}

else if(array[mid] > key)

{

high = mid-1;

}

}

return -1;

}

int main()

{

int number_of_elements;

scanf("%d",&number_of_elements);

int array[number_of_elements];

int iter;

/*Input has to be sorted in non decreasing order */

for(iter = 0;iter < number_of_elements;iter++)

{

scanf("%d",&array[iter]);

}

/* Check if the input array is sorted */

for(iter = 1;iter < number_of_elements;iter++)

{

if(array[iter] < array[iter - 1])

{

printf("Given input is not sorted\n");

return 0;

}

}

int key;

scanf("%d",&key);

/* Calling this functions searches for the key and returns its index. It returns -1

if key is not found.*/

int index;

index = BinarySearch(array,number_of_elements,key);

if(index==-1)

{

printf("Element not found\n");

}

else

{

printf("Element is at index %d\n",index);

}

return 0;

}