Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
binary search

Binary Search In Data Structure

Ankit Kochar

Last Updated on September 22, 2023 by Mayank Dham

In this blog, we will talk about binary search in data structure. Binary Search is one of the most curious topics of data structures as it decreases the time complexity for searching an element in the array from O(N) to O(logN). Not only this, we will also discuss the advantages, drawbacks, applications, and when to use binary search in data structure. Let’s walk slowly and discuss what is binary search in data structure and how to implement binary search in data structure in different languages.

Definition: Binary Search In C Language

Binary Search is a searching technique used in a sorted array by repeatedly dividing the search interval in half. Utilizing the knowledge that the array is sorted, the binary search focuses on decreasing the time complexity to O(LogN).
With this method, an array’s middle is always searched for the element.

Note: A sorted list of items is the only type of list on which a binary search can be used. We must first sort the elements if they are not already sorted.

Dry Run For Binary Search In C Language

There are two techniques to implement binary search algorithms, which are explained below.

  • Iterative Method
  • Recursive Method

The divide and conquer strategy is used in the recursive approach.
The general procedures for both approaches are covered here.

  1. The array that will be used for searching is as follows:

Let x = 4 serve as the search element.

  1. Place two pointers in the lowest and highest positions, respectively, at low and high.

  1. Determine the array’s middle element, arr[(low + high)/2], which equals 6.

  1. Return mid if x == mid. Otherwise, compare the searchable element with m.

  2. If x > mid, evaluate x against the middle element of the elements to its right. Setting low to low = mid + 1 achieves this.

  3. Else, make a comparison of x with the element in the middle of the elements to the left of mid. Setting high to high = mid – 1 accomplishes this.

  1. Carry on in this manner until low and high are met.

  1. x = 4 is found.

Pseudocode for Binary Search Algorithm

Here, we will see the pseudocode for binary search in data structure in both iterative as well as recursive methods.

Iteration Method

do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1

Recursive Method

binarySearch(arr, x, low, high)
    if low > high
        return False 
    else
        mid = (low + high) / 2 
        if x == arr[mid]
            return mid
        else if x > arr[mid]        // x is on the right side
            return binarySearch(arr, x, mid + 1, high)
        else                               // x is on the right side
            return binarySearch(arr, x, low, mid - 1)

Code Implementation of Iterative Method For Binary Search In C language

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int x = 4;
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
  return 0;
}
#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}
class BinarySearch {
  int binarySearch(int array[], int x, int low, int high) {

    while (low <= high) {
      int mid = low + (high - low) / 2;

      if (array[mid] == x)
        return mid;

      if (array[mid] < x)
        low = mid + 1;

      else
        high = mid - 1;
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("Not found");
    else
      System.out.println("Element found at index " + result);
  }
}
def binarySearch(array, x, low, high):

    while low <= high:
        mid = low + (high - low)//2
        if array[mid] == x:
            return mid
        elif array[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Code Implementation of Recursive Method For Binary Search In C langauge

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // If found at mid, then return it
    if (array[mid] == x)
      return mid;

    // Search the left half
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // Search the right half
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int x = 4;
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}
#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // If found at mid, then return it
    if (array[mid] == x)
      return mid;

    // Search the left half
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // Search the right half
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}
class BinarySearch {
  int binarySearch(int array[], int x, int low, int high) {

    if (high >= low) {
      int mid = low + (high - low) / 2;

      // If found at mid, then return it
      if (array[mid] == x)
        return mid;

      // Search the left half
      if (array[mid] > x)
        return binarySearch(array, x, low, mid - 1);

      // Search the right half
      return binarySearch(array, x, mid + 1, high);
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("Not found");
    else
      System.out.println("Element found at index " + result);
  }
}
def binarySearch(array, x, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # If found at mid, then return it
        if array[mid] == x:
            return mid

        # Search the left half
        elif array[mid] > x:
            return binarySearch(array, x, low, mid-1)

        # Search the right half
        else:
            return binarySearch(array, x, mid + 1, high)

    else:
        return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Binary Search in C language Complexity

Let’s discuss the time and space complexity for binary search in data structure.

Time Complexities of Binary search in C language

  • Best case complexity: O(1)
  • Average case complexity: O(log n)
  • Worst case complexity: O(log n)

Space Complexity of Binary Search in C language

The space complexity of the binary search is O(1).

Advantages of Binary Search In C language:

  • Particularly for big arrays, binary search is quicker than linear search. The time it takes to complete a linear search grows linearly while the time it takes to complete a binary search grows logarithmically as the size of the array grows.
  • In comparison to other search algorithms with a comparable time complexity, such interpolation search or exponential search, binary search is more effective.
  • A binary search is a suitable option for many applications because it is practical and straightforward to understand.
  • A binary search is a versatile approach since it can be applied to both sorted arrays and sorted linked lists.
  • Large datasets kept in external memory, such as a hard drive or the cloud, are best searched via binary search.
  • For more complex algorithms, such as those used in computer graphics and machine learning, binary search can be utilized as a building block.

Drawbacks of Binary Search In C Language:

  • The array must be sorted for us. Before running the search, we must first sort the array if it is not already sorted. The sorting step now has an additional O(N logN) time complexity, which can reduce the efficiency of binary search for very tiny arrays.
  • The array being searched must be kept in a set of contiguous memory locations in order to use binary search. If the array is too big to fit in memory or is saved on external memory, such a hard drive or the cloud, this could be an issue.
  • The array’s items must be similar, which means they must be able to be sorted, in order for binary search to work. If the array’s elements are not naturally arranged or the ordering is unclear, this could be an issue.
  • When it comes to exploring really huge datasets that don’t fit in memory, binary search can be less effective than other techniques like hash tables.

Applications of Binary Search In C Language:

  • Binary search can be used as a building block for more complicated machine learning algorithms, such as those that train neural networks or identify the best hyperparameters for a model.
  • Used frequently in competitive programming.
  • Can be applied to computer graphics searches. The simpler binary search strategy can be used as a building element for more sophisticated computer graphics algorithms like ray tracing or texture mapping.
  • Can be applied to database searches. A client database or a catalog of products are two examples of databases containing records that may be efficiently searched using binary search.

When to use Binary Search In C language:

  • With a time complexity of O(log n), it is substantially faster than linear search when searching a huge dataset.
  • When the dataset has been sorted.
  • When memory is contiguous and data is stored there.
  • Data does not have complex relationships or structures.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post