In this tutorial we will learn about Binary Search algorithm to search an item from a given set of items.

In this search technique we divide the given array into two halves at each level and look for the key element in one of the two halves.

This algorithm works only for sorted array.

It is similar to searching a word in a dictionary. We roughly start from the middle. If we are look for a word starting with let's say E then we discard the other half and look in the first half and repeat the process till we find the result.

- It works only for sorted array.
- At each level the array is halved and the key is searched in any one of the half while the other half is rejected.
- Best case occurs when the key we are looking for is present in the middle of the array.
- Worst case occurs when the key is not present.

```
/**
* a[0:n-1] is an array of n elements. key is the element being searched.
*/
BinarySearch(a, n, key)
Begin
Set start = 0, end = n-1, mid = (start + end)/2;
while( start <= end && a[mid] != key) do
if (key < a[mid]) then
Set end = mid – 1; //search in the left half
else
Set start = mid + 1; //search in the right half
endif
Set mid = (start + end)/2;
endwhile
if(start > end)
return -1; //key not found
return mid; //returning key index
End
```

If there are `n`

elements in a given array. Then in each level the array is halved and the search is reduced to one half of the array.

Therefore, if there are `n`

elements then it will require `floor(log`

iterations.
_{2}n+1)

So, we can write order as O(log_{2}n).

```
#include <stdio.h>
//function declaration
int binarySearch(int *a, int n, int key);
int main(){
//variable declaration
int arr[10], i, key;
//input
printf("Enter elements of the array: ");
for(i = 0; i < 10; i++)
scanf("%d", &arr[i]);
printf("Enter key: ");
scanf("%d", &key);
//search
i = binarySearch(arr, 10, key);
//output
if(i == -1)
printf("Key not found.\n");
else
printf("Key at index: %d\n", i);
return 0;
}
//function definition
int binarySearch(int *a, int n, int key){
int start = 0, end = n - 1, mid = (start + end) / 2;
while(start <= end && a[mid] != key){
if(key < a[mid])
end = mid - 1;
else
start = mid + 1;
mid = (start + end) / 2;
}
if(start > end)
return -1; //key not found
return mid;
}
```

- Find XOR of 1 to n Programming
- Finding nth Fibonacci number Programming
- Number Conversion - Binary Octal Hexadecimal Conversion
- Octal to Decimal conversion of an integer number Conversion
- How to install RabbitMQ on Mac using Homebrew How to Mac
- What is EMI? Money
- What is Recurring Deposit? Money
- What is Fixed Deposit? Money
- Sum of Products and Product of Sums Boolean Algebra
- How to install Apache, MySQL, PHP on macOS Mojave 10.14 How to Mac