GL_BinarySearch
  1. What is Binary Search?
  2. Binary Search Pseudocode
  3. Binary Search Algorithm
  4. Binary Search Time Complexity
  5. Binary Search Space Complexity
  6. Binary Search in C
  7. Binary Search in JAVA
  8. Binary Search in C++
  9. Binary Search in Python
  10. Binary Search Example

What is Binary Search?

Binary Search Algorithm is one of the widely used searching techniques. It can be used to sort arrays. This searching technique follows the divide and conquer strategy. The search space always reduces to half in every iteration.

Binary Search Algorithm is a very efficient technique for searching but it needs some order on which partition of the array will occur.

  1. We are given an input array that is supposed to be sorted in ascending order.
  2. We take two variables which will act as a pointer i.e, beg, and end.
  3. Beg will be assigned with 0 and the end will be assigned to the last index of the array.
  4. Now we will introduce another variable mid which will mark the middle of the current array. That will be computed as (low+high)/2.
  5. If the element present at the mid index is equal to the element to be searched, then just return the mid index.
  6. If the element to be searched is smaller than the element present at the mid index, move end to mid-1, and all RHS will get discarded.
  7. If the element to be searched is greater than the element present at the mid index, move beg to mid+1, and all LHS will get discarded.

Iterative approach

binarySearch(arr, size)
		   loop until beg is not equal to end
    midIndex = (beg + end)/2
    if (item == arr[midIndex] )
        return midIndex
    else if (item > arr[midIndex] ) 
        beg = midIndex + 1
    else                       
        end = midIndex - 1

Recursive approach

binarySearch(arr, item, beg, end)
    if beg<=end
        midIndex = (beg + end) / 2 
        if item == arr[midIndex]
            return midIndex
        else if item < arr[midIndex]        
            return binarySearch(arr, item, midIndex + 1, end)
        else                              
            return binarySearch(arr, item, beg, midIndex - 1)
    
    return -1

Binary Search Algorithm Dry Run

Item to be searched=20

input:

01234
1011162023

beg=0, end=4, mid=2

01234
1011162023

beg=3, end=4, mid=3

01234
1011162023

Element found at index 3, Hence 3 will get returned

  • In each iteration, the search space is getting divided by 2. That means that in the current iteration you have to deal with half of the previous iteration array.
  • And the above steps continue till beg<end
  • Best case could be the case where the first mid-value get matched to the element to be searched
  • Best Time Complexity: O(1)
  • Average Time Complexity: O(logn)
  • Worst Time Complexity: O(logn)
  • No auxiliary space is required in Binary Search implementation
  • Hence space complexity: O(1)
#include <stdio.h>

int binarySearch( int arr[], int item, int beg, int end) {
  while (beg <= end) {
    int midIndex = beg + (end - beg) / 2;

    if (arr[midIndex] == item)
      return midIndex;

    if (arr[midIndex] > item)
      beg = midIndex + 1;

    else
      end = midIndex - 1;
  }

  return -1;
}


int main(void) {
  int arr[] = {13, 45, 65, 16, 117, 82, 19};
  int n = sizeof(arr) / sizeof(arr[0]);
  int item = 45;
  int ans = binarySearch(arr, item, 0, n - 1);
  if (ans == -1)
    printf("Element not present");
  else
    printf("answer: %d", ans);
  return 0;
}



Output of the program:
	answer: 1
class BinarySearch {
  int binarySearch(int arr[], int item, int beg, int end) {
    while (beg <= end) {
      int midIndex = beg + (end - beg) / 2;

      if (arr[midIndex] == item)
        return midIndex;

      if (arr[midIndex] > item)
        beg = midIndex + 1;

      else
        end = midIndex - 1;
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {13, 45, 65, 16, 117, 82, 19};
    int n = arr.length;
    int item = 45;
    int ans = ob.binarySearch(arr, item, 0, n - 1);
    if (ans == -1)
      System.out.println("Element not present");
    else
      System.out.println("answer: "+ans);
  }
}


Output of the program:
answer: 1




#include <iostream>
using namespace std;

int binarySearch(int arr[], int item, int beg, int end) {
  
  while (beg <= end) {
    int midIndex = beg + (end - beg) / 2;

    if (arr[midIndex] == item)
      return midIndex;

    if (arr[midIndex] > item)
      beg = midIndex + 1;

    else
      end = midIndex - 1;
  }

  return -1;
}

int main(void) {
  int arr[] = {13, 45, 65, 16, 117, 82, 19};
  int n = sizeof(arr) / sizeof(arr[0]);
  int item = 45;
  int ans = binarySearch(arr, item, 0, n - 1);
  if (ans == -1)
    printf("Element not present");
  else
    printf("answer: %d", ans);
}

Output of the program:
answer: 1



def binarySearch(arr, item, beg, end):

    
    while beg <= end:

        mid = beg + (end - beg)//2

        if arr[mid] == item:
            return mid

        elif arr[mid] > item:
            beg = mid + 1

        else:
            end = mid - 1

    return -1


arr = [13, 45, 65, 16, 117, 82, 19]
item = 45

ans = binarySearch(arr, item, 0, len(arr)-1)

if ans != -1:
    print("answer: " + str(ans))
else:
    print("Element not present")



Output of the program:
answer: 1

#include <stdio.h>


int binarySearch(int arr[], int item, int beg, int end) {
  if (end >= beg) {
    int midIndex = beg + (end - beg) / 2;

    if (arr[midIndex] == item)
      return midIndex;

    if (arr[midIndex] < item)
      return binarySearch(arr, item, beg, midIndex - 1);

    return binarySearch(arr, item, midIndex + 1, end);
  }

  return -1;
}


int main(void) {
  int arr[] = {13, 45, 65, 16, 117, 82, 19};
  int n = sizeof(arr) / sizeof(arr[0]);
  int item = 45;
  int ans = binarySearch(arr, item, 0, n - 1);
  if (ans == -1)
    printf("Element not present");
  else
    printf("answer: %d", ans);
  return 0;
}



Output of the program:
           answer: 1

class BinarySearch {
    int binarySearch(int arr[], int item, int beg, int end) {

    if (end >= beg) {
      int midIndex = beg + (end - beg) / 2;

      if (arr[midIndex] == item)
        return midIndex;

      if (arr[midIndex] < item)
        return binarySearch(arr, item, beg, midIndex - 1);

      return binarySearch(arr, item, midIndex + 1, end);
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {13, 45, 65, 16, 117, 82, 19};
    int n = arr.length;
    int item = 45;
    int ans = ob.binarySearch(arr, item, 0, n - 1);
    if (ans == -1)
      System.out.println("Element not present");
    else
      System.out.println("answer: "+ans);
  }
}



Output of the program:
answer: 1


Recursive Binary Search in C++ 

#include <iostream>
using namespace std;

int binarySearch(int array[], int item, int beg, int end) {
  if (end >= beg) {
    int midIndex = beg + (end - beg) / 2;

    if (array[midIndex] == item)
      return midIndex;

    if (array[midIndex] < item)
      return binarySearch(array, item, beg, midIndex - 1);

    return binarySearch(array, item, midIndex + 1, end);
  }

  return -1;
}

int main(void) {
  int arr[] = {13, 45, 65, 16, 117, 82, 19};
  int n = sizeof(arr) / sizeof(arr[0]);
  int item = 45;
  int ans = binarySearch(arr, item, 0, n - 1);
  if (ans == -1)
    printf("Element not present");
  else
    printf("answer: %d", ans);
}



Output of the program:
answer: 1

Recursive Binary Search in Python


def binarySearch(arr, item, beg, end):

    if end >= beg:

        midIndex = beg + (end - beg)//2

        if arr[midIndex] == item:
            return midIndex

        elif arr[midIndex] < item:
            return binarySearch(arr, item, beg, midIndex-1)

        else:
            return binarySearch(arr, item, midIndex + 1, end)

    else:
        return -1

arr = [13, 45, 65, 16, 117, 82, 19]
item = 45

ans = binarySearch(arr, item, 0, len(arr)-1)

if ans != -1:
    print("answer: " + str(ans))
else:
    print("Element not present")





Output of the program:
answer: 1

Example1:

Your task is to find the first and last occurrence of the given element in the array. If an element is not present, return -1. Assuming sorting here is in ascending order.

Example:

Input

7

1 2 5 5 5 5 6 

5

Output

2 5

Code in Java:

import java.util.*;

class Demo {
	public static void main ( String[] args ) {
		    Scanner sc = new Scanner( System.in );
		    int n = sc.nextInt();
		    int[] arr = new int[n];
		    for( int i = 0 ; i < n ; i++ )
		    {
		        arr[i] = sc.nextInt();
		    }
		    int item = sc.nextInt();
		    int beg = 0, end = 0;
		    for( int i = 0 ; i < n ; i++ )
		    {
		        if( arr[i] == item )
		        {
		            beg = i;
		            break;
		        }
		        else{
		            beg = -1;
		        }
		    }
		    for( int i = arr.length - 1 ; i > 0; i-- )
		    {
		        if( arr[i] == item )
		        {
		            end = i;
		            break;
		        }
		    }
		    if(beg == -1)
		    {
		        System.out.println( -1 );
		    }
		    
		    else {
		        System.out.println( beg + " " + end );
		    }
		    
	}
}

Code in C++:

#include <iostream>
using namespace std;


int main(void) {
           
            int n;
            cin>>n;
            int arr[n];
            for( int i = 0 ; i < n; i++)
              cin>>arr[i];
            
            int item;
            cin>>item;
            int beg = 0, end = 0;
		    for( int i = 0 ; i < n ; i++ )
		    {
		        if( arr[i] == item )
		        {
		            beg = i;
		            break;
		        }
		        else{
		            beg = -1;
		        }
		    }
		    for( int i = n - 1 ; i > 0; i-- )
		    {
		        if( arr[i] == item )
		        {
		            end = i;
		            break;
		        }
		    }
		    if(beg == -1)
		    {
		        cout<<"-1";
		    }
		    
		    else {
		        cout<<beg<<" "<<end;
		    }
		    
	
}

Code in C:

#include <stdio.h>

int main() {
            int n;
            scanf("%d ", &n);
            int arr[n];
            for( int i = 0 ; i < n; i++)
              scanf("%d ",&arr[i]);
            
            int item;
            scanf("%d ",&item);
            int beg = 0, end = 0;
		    for( int i = 0 ; i < n ; i++ )
		    {
		        if( arr[i] == item )
		        {
		            beg = i;
		            break;
		        }
		        else{
		            beg = -1;
		        }
		    }
		    for( int i = n - 1 ; i > 0; i-- )
		    {
		        if( arr[i] == item )
		        {
		            end = i;
		            break;
		        }
		    }
		    if(beg == -1)
		    {
		        printf("%d ",-1);
		    }
		    
		    else {
		        printf("%d %d",beg,end);
		    }
}



This brings us to the end of the blog on Binary Search Algorithm. We hope that you enjoyed it and were able to learn the concept of Binary Search Algorithm well. If you wish to upskill, you can check out Great Learning Academy’s Free online courses!

1

LEAVE A REPLY

Please enter your comment!
Please enter your name here

one × two =