# Binary Search Algorithm- Fundamentals, Implementation and Analysis

Binary Search Algorithm and its Implementation

In our previous tutorial we discussed about Linear search algorithm which is the most basic algorithm of searching which has some disadvantages in terms of time complexity, so to overcome them to a level an algorithm based on dichotomic (i.e. selection between two distinct alternatives) divide and conquer technique is used i.e. Binary search algorithm and it is used to find an element in a sorted array (yes, it is a prerequisite for this algorithm and a limitation too).

In this algorithm we use the sorted array so as to reduce the time complexity to O(log n). In this, size of the elements reduce to half after each iteration and this is achieved by comparing the middle element with the key and if they are unequal then we choose the first or second half, whichever is expected to hold the key (if available) based on the comparison i.e. if array is sorted in an increasing manner and the key is smaller than middle element than definitely if key exists, it will be in the first half, we chose it and repeat same operation again and again until key is found or no more elements are left in the array.

#### Recursive Pseudocode:

```// initially called with low = 0, high = N – 1
BinarySearch_Right(A[0..N-1], value, low, high) {
// invariants: value >= A[i] for all i < low
value < A[i] for all i > high
if (high < low)
return low
mid = low +((high – low) / 2) // THIS IS AN IMPORTANT STEP TO AVOID BUGS
if (A[mid] > value)
return BinarySearch_Right(A, value, low, mid-1)
else
return BinarySearch_Right(A, value, mid+1, high)
}
```

#### Iterative Pseudocode:

``` BinarySearch_Right(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
// invariants: value >= A[i] for all i < low
value < A[i] for all i > high
mid = low +((high – low) / 2) // THIS IS AN IMPORTANT STEP TO AVOID BUGS
if (A[mid] > value)
high = mid - 1
else
low = mid + 1
}
return low
}
```

#### Asymptotic Analysis

Since this algorithm halves the no of elements to be checked after every iteration it will take logarithmic time to find any element i.e. O(log n) (where n is number of elements in the list) and its expected cost is also proportional to log n provided that searching and comparing cost of all the elements is same

Data structure used -> Array
Worst case performance -> O(log n)
Best case performance -> O(1)
Average case performance -> O(log n)
Worst case space complexity -> O(1)

So the idea is-

1. Compare the key (element to be searched) with the mid element.
2. If key matches with middle element, we return the mid index.
3. Else If key is greater than the mid element, then key can only lie in right half subarray after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half until there are no more elements left in the array.

#### RECURSIVE Implementation of Binary search in C programming language

```#include <stdio.h>

// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;

// If the element is present at the middle itself
if (arr[mid] == x)  return mid;

// If element is smaller than mid, then it can only be present
// in left subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}

// We reach here when element is not present in array
return -1;
}

int main(void)
{
int arr[] = {2, 3, 4, 5, 10, 15, 25, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 15;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}

```
```Output:-

Element is present at index 5```

#### ITERATIVE Implementation of Binary search in C programming language

```#include <stdio.h>

// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;

if (arr[m] == x) return m;  // Check if x is present at mid

if (arr[m] < x) l = m + 1; // If x greater, ignore left half

else r = m - 1; // If x is smaller, ignore right half
}
return -1; // If this line executes, then search was unsuccessful i.e. element is not present
}

int main(void)
{
int arr[] = {2, 3, 4, 5, 10, 15, 25, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 15;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
```
```Output:-

Element is present at index 5
```

#### Implementation of BinarySearch(Iterative and Recursive methods) in Java

In Java Binary Search method is already implemented and it is recommended that we should use `java.util.Arrays.binarySearch(//A lot of overloaded functions)`. See complete list of functions here – Oracle – java.util.Arrays

```package com.codingeek.algorithms;

public class RecursiveBinarySearchAlgorithm {

public static int recursiveBinarySearch(int[] sortedArray, int start, int end, int key) {

if (start < end) {
int mid = start + (end - start) / 2;
if (key < sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, start, mid, key);

} else if (key > sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, mid+1, end , key);

} else {
return mid;
}
}
return -1;
}

public static void main(String[] args) {

int[] arr1 = {2,45,100,190,280,500,670,700,999};
int index = recursiveBinarySearch(arr1,0,arr1.length,45);
if(index != -1){
System.out.println("Found 45 at "+index+" index");
}
else{
}

index = recursiveBinarySearch(arr1,0,arr1.length,99);
if(index != -1){
System.out.println("Found 999 at "+index+" index");
}else{
}
}
}
```
```Output:-

Found 45 at 1 index

```

IMPORTANT NOTE :- One important point was that while finding the mid-point we do (mid = low +((high – low) / 2)) while this can also be achieved by simply doing (mid =(high + low) / 2)). This is because if both the numbers i.e. low and high are too high such that their sum reaches above the range of datatype used then it will produce an error as it will become a negative number and no array index of negative value is possible.

For ex – if low = 32,000 and high = 32,700 then
mid = (32000 + 32700)/2 = 64700/2
In C Language => 64700 for an “int” type is equal to (-835)
i.e. (-835)/2 = (-417), which will produce error.

So to avoid such situations we add the half of difference between the two to the lower value which ensures that we never encounter such a situation.

### Recommended -

• Thanks Hitesh. Really worthy knowledge. The part I mostly liked is the recursive and iterative approach for same problem.

What’s the guarantee that the binary search algorithm that we are using is gonna find the element?

• hiteshgarg21

If there is an element in the array or list then definitely it will find the element.