DSA Binary Search

DSA Binary Search – Complete Beginner Guide

(Concept • Manual Run-Through • Algorithm • Code • Time Complexity)

Binary Search is a fast and efficient searching algorithm in Data Structures & Algorithms (DSA).
It works by dividing the search space into halves.

1️⃣ What is Binary Search?

Binary Search:

Works only on sorted arrays
Compares the target with the middle element
Eliminates half of the search space each step
Repeats until element is found or range becomes empty

Also called Half-Interval Search.

2️⃣ Simple Idea (One Line)

Check middle → discard half → repeat

3️⃣ When to Use Binary Search?

✔ Array must be sorted
✔ Large datasets
✔ Faster than Linear Search

❌ Unsorted arrays (must sort first)

4️⃣ Binary Search – Manual Run-Through

Sorted Array

Target Value

Step 1

Match Found

Element found at index 3.

Another Example (Not Found Case)

Target = 10

Step	mid	Value	Action
1	3	15	Search left
2	1	7	Search right
3	2	11	Search left
—	—	—	Not found

5️⃣ Binary Search Algorithm (Steps)

Start
Set low = 0, high = n - 1
While low ≤ high
Calculate mid = (low + high) / 2
If arr[mid] == key → return index
If arr[mid] > key → search left half
Else → search right half
If not found → return -1
Stop

6️⃣ Pseudocode

7️⃣ Binary Search Implementation (C++)

Iterative Method

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;

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

if(arr[mid] == key)
return mid;
else if(arr[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}

int main() {
int arr[] = {3, 7, 11, 15, 18, 22, 30};
int n = 7;
int key = 15;

int result = binarySearch(arr, n, key);

if(result != -1)
cout << "Element found at index " << result;
else
cout << "Element not found";

return 0;
}

#include <iostream>

using namespace std;

int binarySearch(int arr[], int n, int key) {

int low = 0, high = n - 1;

while(low <= high) {

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

if(arr[mid] == key)

return mid;

else if(arr[mid] > key)

high = mid - 1;

else

low = mid + 1;

}

return -1;

}

int main() {

int arr[] = {3, 7, 11, 15, 18, 22, 30};

int n = 7;

int key = 15;

int result = binarySearch(arr, n, key);

if(result != -1)

cout << "Element found at index " << result;

else

cout << "Element not found";

return 0;

}

Output

8️⃣ Recursive Binary Search

int binarySearch(int arr[], int low, int high, int key) {
if(low <= high) {
int mid = low + (high - low) / 2;

if(arr[mid] == key)
return mid;
else if(arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
else
return binarySearch(arr, mid + 1, high, key);
}
return -1;
}

int binarySearch(int arr[], int low, int high, int key) {

if(low <= high) {

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

if(arr[mid] == key)

return mid;

else if(arr[mid] > key)

return binarySearch(arr, low, mid - 1, key);

else

return binarySearch(arr, mid + 1, high, key);

}

return -1;

}

9️⃣ Time Complexity

Case	Time Complexity
Best Case	O(1)
Average Case	O(log n)
Worst Case	O(log n)

Each step reduces search space by half.

🔟 Space Complexity

Method	Space
Iterative	O(1)
Recursive	O(log n) (call stack)

1️⃣1️⃣ Advantages of Binary Search

✔ Very fast
✔ Efficient for large datasets
✔ Minimal comparisons

1️⃣2️⃣ Disadvantages of Binary Search

❌ Requires sorted data
❌ Not suitable for linked lists
❌ Sorting overhead if data is unsorted

1️⃣3️⃣ Binary Search vs Linear Search

Feature	Linear	Binary
Sorted data	Not required	Required
Time	O(n)	O(log n)
Speed	Slow	Fast
Use case	Small data	Large data

Exam / Interview Questions (Binary Search)

Q1. Why is Binary Search faster?
👉 It halves the search space each step

Q2. Can Binary Search work on unsorted array?
👉 No

Q3. Best case time complexity?
👉 O(1)

Final Summary

✔ Binary Search works on sorted arrays
✔ Divide-and-conquer strategy
✔ Time complexity: O(log n)
✔ Space complexity: O(1) iterative
✔ Essential for DSA & interviews

DSA Binary Search