Binary Search in C

Introduction

Binary search is a robust algorithm with various applications aiming to serve its purpose across aspects of computer science, numerical solutions, data processing, and many more. In C programming, binary search can be implemented using iterative or recursive approaches. The algorithm's efficiency and simplicity make it a fundamental tool for searching and other related operations in various applications.

How Does Binary Search Work?

The most widely used algorithm in the C programming language, Binary Search, primarily takes a divide-and-conquer approach to determine the target value within a sorted array.

Here is a detailed guide to facilitate your understanding of how binary search in C exactly operates.

• Let’s say we have an array named ‘o’.
• Binary search commences by setting two pointers, named ‘start’ and ‘end’ at the first and last indices of the array.
• Following this, we use the formula ‘mid = (start+end) / 2’ to compute the middle index of the search space.
• If the target value is equal to the element in the middle index, it means that the target is found, and we can terminate the search.
• In case the target value is less than the middle element, then we have to update the ‘end’ variable to be ‘mid - 1’. If the target value is greater than the middle element, then we update the ‘start; variable' to be ‘mid + 1’.

We have to continue computing the middle index and adjust the search space until it becomes empty, that is, start > end. When this happens, and the target value is not found, it denotes that the target value does not exist in the array. At this point, we can either return a special value or perform any desired action to highlight that the target value was not found.

When to use Binary Search?

Binary search is not only limited to finding a specific target value in a sorted array but can be applied in various other scenarios. Here are some common use cases for binary search:

• Large Sorted Arrays - When dealing with large sorted arrays, it is always advisable to use binary search in C. It can quickly locate the target value with a significantly small number of comparisons.
• Efficient Element Retrieval - Binary search in C is also useful in locating the position or index of a value in a sorted array. This is especially beneficial when you have to update any specific element in the array based on its values.
• Range Queries - Binary search in C can also address range queries in sorted arrays. This technique allows you to accurately identify the first or last occurrence of a value within a specified range.
• Implementing Data Structures - Lastly, binary search in C can bear effective results in implementing other data structures, such as binary search trees or skip lists. Furthermore, it also enables you to perform insertion and deletion operations in a quick and hassle-free manner.

How to Implement Binary Search?

There are two main approaches for implementing the binary search algorithm. These approaches are:

• Iterative Binary Search
• Recursive Binary Search

Iterative Binary Search

Iterative binary search, as the name suggests, is when the algorithm uses a loop-based approach to efficiently search for a target value with a sorted array.

The basic structure of iterative binary search in C goes as follows,

#include <stdio.h>
int binarySearch(int array[], int size, int target) {
int startIndex = 0;
int endIndex = size - 1;
while (startIndex <= endIndex) {
int midIndex = startIndex + (endIndex - startIndex) / 2;
if (array[midIndex] == target) {
return midIndex; // Target value found at index mid
} else if (array[midIndex] < target) {
startIndex = midIndex + 1; // Target value is in the upper half
} else {
endIndex = midIndex - 1; // Target value is in the lower half
}
}
return -1; // Target value not found in the array
}
int main() {
// Example usage
int array[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int size = sizeof(array) / sizeof(array[0]);
int target = 23;
int result = binarySearch(array, size, target);
if (result != -1) {
printf("Target value found at index %d\n", result);
} else {
printf("Target value not found in the array\n");
}
return 0;
}

Recursive Binary Search

Contrary to the former, recursive binary search is used when the algorithm adapts to a recursive approach to locate the target value with a sorted array. This means that instead of using the loop, the array is divided in half and recursively calls itself on the appropriate subarray. This continues till the target value is found or the search space is exhausted.

Let’s take a look at a small example of using recursive binary search in C,

#include <stdio.h>
int binarySearch(int array[], int startIndex, int endIndex, int target) {
if (startIndex <= endIndex) {
int midIndex = startIndex+ (endIndex - startIndex) / 2;
if (array[midIndex] == target) {
return midIndex; // Target value found at index mid
} else if (array[midIndex] < target) {
return binarySearch(array, midIndex + 1, endIndex, target); // Recursively search in the upper half
} else {
return binarySearch(array, startIndex, midIndex - 1, target); // Recursively search in the lower half
}
}
return -1; // Target value not found in the array
}
int main() {
// Example usage
int array[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int size = sizeof(array) / sizeof(array[0]);
int target = 23;
int result = binarySearch(array, 0, size - 1, target);
if (result != -1) {
printf("Target value found at index %d\n", result);
} else {
printf("Target value not found in the array\n");
}
return 0;
}

Conditions for When to Apply Binary Search in a Data Structure

To apply binary search in a data structure, it needs to meet two specific conditions. They are, namely,

Sorted Data

The data structure must be sorted either in ascending order or descending for the binary search. Furthermore, the elements must also be arranged accordingly so that it can allow identification and comparison of the target value.

Random Access

Secondly, binary search bears fruitful results when random access to elements is allowed. Thus, you can access the elements quite easily through their indices.

Once both these conditions have been satisfied, you can apply binary search on multiple data structures, including arrays, and balanced binary search trees, among others. Please note that binary search is not at all advisable for unsorted arrays since it can generate unwanted results. In such cases, using other tools, such as hashing or linear search, is best.

Binary Search Complexity Analysis:

Various search algorithms are used in computer science to look for an element in a list. To understand and compare the efficiency of each of those algorithms, we primarily use space and time complexities.

Space and Time Complexity of Binary Search Algorithm

Space and time complexities of binary search algorithms enable it to quickly retrieve elements and outperform other tools, such as linear search, especially when dealing with large data sets.

Time Complexity

The time complexity is logarithmic. This means that the search space is broken in half with each comparison. One of the major benefits of this approach is that the number of comparisons usually required for finding the target element remains small, even in large input sizes.

• O(1) Best Case - It is when the target element is located in the middle index during the first comparison.
• O(log N) Worst Case - It is when the target element is situated either in the first or last element in the array or not present in the array at all.

Space Complexity

Space complexity denotes the memory usage for programs that have large inputs. It is usually constant, meaning that the additional amount of memory used will always remain constant irrespective of the input size.

• O(1) - Iterative method
• O(log N) - Recursive method.

The correct way to calculate “mid” in Binary Search

The middle index in binary search is calculated by generating an average of the lower index ‘low’ and higher index ‘high. The syntax for the same goes as follows,

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

This is especially useful when you are handling large indices and prevents the occurrence of integer overflow. However, that being said, please note that simply using (low + high) / 2 might not always generate the desired result. This is because it can often cause an integer overflow when the higher and lower index sum exceeds the maximum value that an integer data type can represent. Therefore, using (high - low) / 2 is always advisable to avoid such issues.

Advantages of Binary Search

Binary search has been deemed an essential tool in various applications, especially where efficient searching is required. It offers many benefits to the users. A few of the same have been highlighted below.

• Easy Implementation - Understanding the basic concept of binary search in C is fairly simple and easy. It involves dividing the search space in half, making comparisons, and updating the search range accordingly. Once you get a hold of this concept, you can quite easily implement the same without facing much hassle.
• Versatility - When it comes to binary search, there is usually no limit to its application. You can use this on multiple data structures such as arrays or sorted array trees.
• Deterministic Behavior - When applied to sorted data structure, binary search in C generates accurate and consistent results. It leaves almost little to no room for errors or incorrect search outcomes, making it the perfect choice for applications requiring accurate searching.

Drawbacks of Binary Search

While citing the advantages of binary search in C, you must also consider the downsides of it as well.

• Requirement of Sorted Data - As stated earlier, binary search can only work when applied to sorted data, either in ascending or descending order. Without the same, a preprocessing step of sorting the data is required. This can be quite time-consuming and also bears the possibility of increasing the overall complexity of the algorithm.
• Lack of dynamic updates - The data structure must remain static for the binary search to work efficiently. This means that any data structure that needs to be updated frequently can hamper its sorted nature, making it quite difficult to perform a binary search.
• Not Applicable on Non-comparable Data - Binary search primarily compares elements to determine the search direction. Therefore, in case you are working with non-comparable data types such as complex objects, the binary search might not generate the desired outcome.

Applications of Binary Search

1. Binary search is primarily used to search elements in a sorted array or a sorted list. It allows for efficient retrieval of elements by repeatedly dividing the search space in half.
2. The binary search algorithm can be utilised for performing other operations, such as finding the smallest element in the array or locating the largest element in the array.

Conclusion

To sum up, binary search is undoubtedly quite an important tool with numerous applications. From data processing to solving range query problems, the list continues. It also brings many advantages to the table, implying its significance. That being said, knowing when to use and how to use binary search is also crucial. Furthermore, some conditions must be fulfilled for binary search to operate properly.

To know more about the same, do not forget to check out upGrad’s MS in Computer Science Program offered under the leading Liverpool John Moores University. The program is specifically curated for aspirants wishing to boost their knowledge and career in programming languages.

So what are you waiting for? Enroll now!

FAQS

Q1: What are the two types of binary search?

Binary search implementation can primarily be done in two ways. They are, namely, recursive binary search and iterative binary search. The former has a space complexity of O(log N), while the latter uses O(1).

Q2: Why is binary search considered to be the best?

Compared to other algorithms, such as Linear search, binary search is much faster to execute and implement. Furthermore, it uses the divide and conquer approach, wherein only half of the list is searched instead of going through every element. For all these reasons, binary search is considered to be the most efficient.

Q3: Can you name some search algorithms?

Linear search, binary search, jump search, exponential search, and Fibonacci search are examples of some of the many search algorithms used by programmers.

Take a Free C Programming Quiz

Answer quick questions and assess your C programming knowledge

Start Quiz