Data Structure and Algorithm
Introduction to Binary Search with Practical Examples
 Binary Search
 Sufficient Conditions for Binary Search
 Working Principle of Binary Search
 Example: Finding a Key in a Sorted Array
 Time Complexity of Binary Search
 Application of Binary Search
Picture yourself searching for a word in a massive dictionary. Instead of flipping through every page randomly, You start by selecting a midpoint in the dictionary and check if the word appears on that page. If you find it, your search ends there. However, if the word isn’t on that page, you narrow down your search to either the previous or next half of the dictionary.
Continuing this process, you progressively divide the dictionary into smaller segments, each time focusing on the segment where the word might be located. Eventually, you pinpoint the exact page where the word resides. This systematic approach mirrors the efficiency of binary search, enabling you to swiftly locate the word without scanning every page.
¶Binary Search
Binary search is a searching algorithm used to find the position of a target value within a sorted array or list. It follows a divideandconquer approach, systematically reducing the search space in each iteration by half. This algorithm is particularly efficient for large datasets as it eliminates half of the remaining elements with each step, resulting in a logarithmic time complexity.
Binary search is applicable to any monotonic characteristic search space, enabling the search for elements that meet specific monotonic conditions within the space. This is because binary search relies on the inherent monotonicity of the search space, simplifying the efficient location of the desired elements within it.
¶Sufficient Conditions for Binary Search

Monotonicity:
The search space must exhibit monotonicity, meaning that the value of elements either consistently increases or consistently decreases as we traverse the data structure. This monotonicity ensures that binary search can reliably determine which half of the search space to explore next. 
Random Access:
Binary search requires the ability to access elements in the data structure in constant time. This is typically achieved through random access, which allows accessing any element in the data structure directly without needing to traverse through the entire structure.
¶Working Principle of Binary Search
Binary Search algorithm works in few steps,

Divide the Search Space:
 Find the middle index “mid” to divide the search space into two halves.

Compare with Middle Element:
 Compare the middle element of the search space with the key.
 If the key is found at the middle element, the process is terminated.

Choose Next Search Space:
 If the key is not found at the middle element, determine which half will be used as the next search space.
 If the key is smaller than the middle element, use the left side for the next search.
 If the key is larger than the middle element, use the right side for the next search.

Continuation of the Process:
 Repeat steps 13 until either:
 The key is found, and the search is successful.
 The total search space is exhausted, indicating that the key is not present.
¶Example: Finding a Key in a Sorted Array
Let’s explore how binary search works by using it to find a key in a sorted array.
¶Satisfies Sufficient Conditions ?

Monotonicity:
Monotonicity refers to the consistent pattern of elements in the array. In a sorted array, elements are arranged either in nondecreasing or nonincreasing order. For example, in a nondecreasing sorted array, each element is greater than or equal to the preceding element. 
Random Access:
Random access implies the ability to directly access any element in the array in constant time. In a sorted array, this means we can quickly access the middle element using its index without needing to traverse the array sequentially.
So, with the sorted array satisfying these conditions, binary search becomes applicable.
¶Binary Search Walkthrough
Sure, let’s walk through the steps of binary search to find the key 5 in the sorted array [1, 3, 5, 6, 7, 12, 19].

Initialization:
 Initially, the search space encompasses the entire array.
 Set
left
pointer to index 0 andright
pointer to index 6.  Calculate the midpoint
 The middle element of the array is 6.

Comparison:
 Compare the key 5 with the middle element 6: Since 5 < 6, we discard the right half of the search space and focus on the left half.

Adjustment of Pointers:
 Update the
right
pointer to mid  1.  The search space now includes only the elements [1, 3, 5].
 Update the

Repeat Steps 13:
 Step 1: Calculate the new midpoint
 The middle element of the remaining search space is 3.
 Step 2: Compare the key 5 with the middle element 3: Since 5 > 3, discard the left half of the search space.

Step 3: Update the
left
pointer to mid + 1.  The search space now includes only the element 5.

Final Comparison:
 The only remaining element in the search space is 5.
 Compare the key 5 with the middle element 5: The key matches the middle element, indicating that the search is successful.

Conclusion:
 The key 5 is found at index 2 in the array [1, 3, 5, 6, 7, 12, 19].
¶Implementation in C
#include <stdio.h>
// Function to perform binary search
int binarySearch(int arr[], int n, int key) {
int left = 0;
int right = n  1;
// Iterate until left pointer is less than or equal to right pointer
while (left <= right) {
// Calculate the midpoint
int mid = left + (right  left) / 2;
// If key is found at the midpoint, return the index
if (arr[mid] == key) {
return mid;
}
// If key is greater than the element at midpoint, search in the right half
else if (arr[mid] < key) {
left = mid + 1;
}
// If key is smaller than the element at midpoint, search in the left half
else {
right = mid  1;
}
}
// If key is not found, return 1
return 1;
}
int main() {
int arr[] = {1, 3, 5, 6, 7, 12, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 5;
// Perform binary search
int index = binarySearch(arr, n, key);
// Print the result
if (index != 1) {
printf("Key %d found at index %d\n", key, index);
} else {
printf("Key %d not found\n", key);
}
return 0;
}
Key 5 found at index 2
¶Time Complexity of Binary Search
The time complexity of binary search is O(log n)
, where n is the number of elements in the array. In each iteration of binary search, the search space is divided in half, effectively halving the number of elements to search through. This logarithmic behavior is due to the fact that the search space is reduced exponentially with each iteration.
¶Application of Binary Search

Debugging Linear Code: Imagine you’re fixing errors in a long sequence of code. Instead of checking each line randomly, binary search helps you identify where the mistake might be. You start by testing the middle section of the code. If it works fine, you know the issue lies after that point. Otherwise, you backtrack to the previous midpoint to search for the bug. This process continues, dividing the code into smaller parts until you find the exact location of the error. This method efficiently isolates bugs, much like how binary search quickly finds a target value in a sorted list.

Searching in Databases: When searching for specific records in a database, binary search speeds up the process. Imagine a massive library catalog. Instead of checking each book randomly, binary search helps you narrow down your search. You start by looking at the middle section of the catalog. If the book you’re looking for is alphabetically after that point, you focus on the second half. Otherwise, you explore the first half. This systematic approach reduces search time, especially when the database is sorted by indexed fields.

File Systems: In a computer’s file system, binary search assists in locating files or directories efficiently. Think of a cluttered filing cabinet. Instead of rummaging through every drawer, binary search helps you navigate the directory tree. You start by checking the midpoint. If the file you’re searching for is alphabetically after that point, you explore the right side. Otherwise, you focus on the left side. This method is particularly useful in large file systems where finding specific files quickly is essential.

Finding Words in Dictionaries: When searching for a word in a dictionary, binary search expedites the process. Imagine a thick dictionary with thousands of words. Instead of flipping through each page randomly, binary search helps you locate the word efficiently. You start by opening the dictionary in the middle. If the word you’re looking for comes later alphabetically, you turn to the latter half. Otherwise, you check the first half. This systematic approach allows for quick access to definitions or translations, especially since dictionaries are often arranged in alphabetical order.

Mathematical Calculations: Binary search aids in various mathematical applications, improving computational efficiency. For instance, when finding roots of equations or locating elements in sorted lists, binary search streamlines the process. Imagine solving a complex equation. Instead of guessing randomly, binary search helps you narrow down the possible solutions. You start by testing the midpoint of the solution range. If the result is too high, you focus on the lower half, and vice versa. This method optimizes mathematical calculations, making them faster and more accurate.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Introduction to Tree Data Structure with Practical Examples
Sliding Window Technique with Two Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development