# 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(l****o****g 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-**

- Compare the key (element to be searched) with the mid element.
- If key matches with middle element, we return the mid index.
- 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.
- 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{ System.out.println("Element not found"); } index = recursiveBinarySearch(arr1,0,arr1.length,99); if(index != -1){ System.out.println("Found 999 at "+index+" index"); }else{ System.out.println("Element not found"); } } }

**Output:-**
Found 45 at 1 index
Element not found

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