π§ The Magic of Smart Searching
A Tale of Sorted Boxes & Smart Moves
A Tale of Two Halves: The Smart Snack Box π«
You're back in your room and spot your snack stash β but this time
itβs super organized.
All your chocolates are sorted in alphabetical order:
[5-Star, Dairy Milk, KitKat, Munch, Perk]
Now, you want to grab your fav β Munch.
But wait! π€ Instead of checking each one (like in linear search),
youβve got a smarter plan this time!
π§ What is Binary Search?
Binary Search is like being a smart detective in a sorted list.
Rather than checking one-by-one, you go straight to the middle!
You divide and conquer!
Cut the list in half
π Check the middle item
π Decide: Go left? Or go right?
Repeat till you find it (or not)!
π― Letβs Do a Dry Run:
Snack box = [5-Star, Dairy Milk, KitKat, Munch, Perk]
You're searching for Munch π«
Letβs turn the story into steps:
β What if itβs not there?
Snack box: [5-Star, Dairy Milk, KitKat, Munch, Perk]
You search for Snickers π« (not in list)
You do the same process:
Middle = KitKat β not Snickers
Move right or left β check β still not there β
Eventually, you return -1 = Not Found.
π Steps to Remember:
Check if the array is sorted β
Set two pointers β low and high
While low <= high:
Find mid = (low + high)/2
Is it the target? β π― Return index!
If target < mid β Move high = mid - 1
If target > mid β Move low = mid + 1
If not found β return -1 β
π§βπ» Code Time! (C++)
int binarySearch(vector<string>& arr, string target) {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1; // Not Found
}
π‘ Quick Recap:
β
Binary Search works only on sorted arrays
Cut the search space in half every time
β‘ Time Complexity: O(log n)
π Way faster than Linear Search!
Real-World Analogy:
Imagine finding a name in a phone book π
Do you start from page 1?
Nope! You flip to the middle π β Then go left or right!
Thatβs Binary Search π‘
π¬ Wrapping Up
Binary Search is like Sherlock Holmes β it doesnβt check everything, it thinks, splits, and finds smartly!
So next time youβre searching something in a sorted list β
Don't be slowβ¦ go Binary! π§
Top comments (0)