Join Our 4-Week Free Gen AI Course with select Programs.

Request a callback

or Chat with us on

Binary Search in C Programming, Explained with Examples.

Basics of SQL
Basics of SQL
icon
12 Hrs. duration
icon
12 Modules
icon
2600+ Learners
logo
Start Learning

Imagine you’re searching for a specific book in a library, but you don’t know where it is. Binary Search is like having a librarian who can quickly guide you to the right shelf. It’s a search algorithm used to find an element in a sorted array or a linked list. This powerful tool is one of the most used algorithms for searching data in a collection of elements.

Binary Search is a sorting algorithm for finding the position of a target value within a sorted array or list. This algorithm repeatedly  divides the search interval in half until the target value is four or the interval is empty. Each step of the binary search algorithm compares the target value with the middle element of the array. If the target is matched with the middle element. Then, It will return the search continuously in the lower half of the array. If the target value is greater, the search will be continuous in the lower half of the array or list. If the target value is greater than the search continuous in the right half. This process is repeated until the desired element is not found or the search interval is empty.

 

Read also: Sorting in Data Structure

Condition to Apply Binary Search Algorithm in a Data Structure

To apply a Binary Search Algorithm in an array data structure or any data structure. This condition must be applied for using the Binary Search algorithm.

 

  • The data structure must be sorted.
  • Access to any element in the data structures takes constant time.

Binary Search Algorithm

In this section, we will see how the Binary Search Algorithm works. 

 

  • First, Divide the Array into two halves 
  • Compare the middle element of the search space with the key attribute.
  • If the key is found in the middle element. Then, processes will be terminated.
  • If the key is not found at the middle element in the array. Choose half will be used as the next search space in the array.
  • If the key is smaller than the middle element, the left side is used to search for the target element.
  • If the key is larger than the middle element, then the right side is used for the next search element.
  • This process is continued until the key is found or the total search space is not available.

How Does Binary Search Algorithm Work?

In this section,  we will see the workings of the binary search algorithm.

 

Consider an array arr[] = {35,44,98,90,100,102,110}

 

  • Find the mid element in the array. Then, compare it with the element with the key. If the key is less than the mid element, move to the left, and if it is greater than the mid, move the search space to the right. 
  • For example, key 110 is greater than the current mid element, for example, 90. The search space moves to the right.
  • The key is less than the current mid in 102. The search space moves to the right-hand side.
  • If the key matches the value of the mid element, stop the search.

How to Implement a Binary Search Algorithm?

The Binary search algorithm can be implemented in two ways

 

  • Iterative Binary Search Algorithm
  • Recursive Binary Search Algorithm

Iterative Binary Search Algorithm

In this section, we will use a Binary Search algorithm in C language using the iterative approach. This method is similar to the recursive method. Let’s dive deep into this method.

 

The following program demonstrates the  iterative approach in Binary Search Algorithm:

 

Program

#include <stdio.h> // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) { while (low <= high) { int mid = low + (high – low) / 2; // Check if x is present at mid if (arr[mid] == x) return mid; // If x is greater, ignore the left half if (arr[mid] < x) low = mid + 1; // If x is smaller, ignore the right half else high = mid – 1; } // If we reach here, then the element was not present return -1; } // Driver code int main(void) { int arr[] = { 343, 888, 1025, 1053, 1984 }; int n = sizeof(arr) / sizeof(arr[0]); int x = 1984; 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 4

 

Time Complexity : O(log N)

Auxiliary Space : O(1)

Recursive Binary Search Algorithm

 

The following program demonstrates the Binary Search Algorithm Recursively.

 

Program

 

#include <stdio.h> int binarySearch(int arr[], int low, int high, int x) { if (high >= low) { int mid = low + (high – low) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, low, mid – 1, x); return binarySearch(arr, mid + 1, high, x); } return -1; } // Driver code int main() { int arr[] = { 93, 343, 599, 790, 1015 }; int n = sizeof(arr) / sizeof(arr[0]); int x = 1015; 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 4
DevOps & Cloud Engineering
Internship Assurance
DevOps & Cloud Engineering

Time Complexity:

 

  • Best Case : O(1)
  • Average Case : O(log N)
  • Worst Case : O(log N)

 

Auxiliary Space: O(1).  If we use call stack in binary search, then auxiliary space will be O(log N).

Application of Binary Search Algorithm

  • Searching in Sorting: Binary  Search algorithm commonly used to efficiently search an element in a sorted array. It works by repeatedly dividing the search interval in half. It is very efficient, with a time complexity of O(log n), where n is the number of elements in the arrays.
  • Graphics: Binary search algorithms, such as those for ray tracing or texture mapping, are also used in computer graphics.
  • Database: It is also used in database searching.

There are many advantages to Binary Search algorithms. Let’s dive deep into it one by one.

 

  • The Binary Search algorithm is faster than a linear search algorithm. We can use binary search for large arrays.
  • It has less compilation time and thus  better time complexity as compared to other algorithms.

Disadvantages of Binary Search Algorithm

  • Binary only works on sorted list or array
  • Binary search requires that the data structure must begin the search and be stored in contiguous memory locations.
  • Binary search requires that the arrays’  elements be comparable, meaning that they must be able to be ordered. 
  • Binary search is not suitable for dynamic data structures like linked lists, where accessing elements by indexing is not efficient.

Conclusion

In this article, we learned about Binary Search in the C programming language. This  powerful algorithm quickly finds elements in sorted arrays. Binary search can drastically improve the performance of search operations compared to linear search algorithms. It is particularly useful in scenarios where the data is stored and needs to be searched repeatedly.

FAQs
Binary search is the best algorithm when you have a sorted list or array. It is very useful when you need to find an element in large datasets where the linear searching algorithm would be slow.
Binary search is faster than linear search only when the data is sorted. If the data is not sorted, a linear search is often more appropriate.
The Binary Search algorithm requires sorted data. If the sorted data is not provided, another search algorithm will be helpful.
Yes, the Binary search algorithm can also be applied to non-numeric data, as there is a defined order for the elements. For example, it can also be used to search for strings in alphabetical order.
Yes, we can implement the binary search algorithm both iteratively and recursively. The recursive approach uses the external space in the memory stack.

Deploying Applications Over the Cloud Using Jenkins

Prashant Kumar Dey

Prashant Kumar Dey

Associate Program Director - Hero Vired

Ex BMW | Google

24 October, 7:00 PM (IST)

Limited Seats Left

Book a Free Live Class

left dot patternright dot pattern

Programs tailored for your success

Popular

Management

Data Science

Finance

Technology

Future Tech

Upskill with expert articles

View all
Hero Vired logo
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
18003093939     ·     hello@herovired.com     ·    Whatsapp
Privacy policy and Terms of use

|

Sitemap

© 2024 Hero Vired. All rights reserved