Welcome to the exciting world of computer science! Today, we are going to learn about a special way to find things called binary search. Imagine you're looking for a specific number in a list of numbers, but instead of checking each number one by one, you have a smart way to find it quickly. Let's dive into it!
What is Binary Search Algorithm?
To explain how the binary search algorithm works, we will use a sorted array. Please note that in some cases, binary search can be adapted for unsorted arrays as well.
Let's consider a sorted array from 1 to 9, and we want to find our target number, which is 3. Our goal is to determine if the array contains the number 3.
Our primary aim is to find the number. If we don't find it or when we find it and what to do that would be explained during the code explanation as at the moment most important thing is how the algorithm works.
At the moment our range points are 1 and 9. Those are the points we are searching between. For better explanation lets say left range point is 1 and right range point is 9.
Let's first find the middle element. If we have 9 elements, the middle one would be the 5th element. (How to find the middle element in general while coding will be shown later.)
Sweet! We found the middle element, which is 5. Remember, our target is 3. Now, let's consider some questions:
Is the target lower than middle which means target < middle 3 < 5
Is the target greater than middle which means target > middle 3 > 5
Is the target equal to our middle which means target = middle 3 = 5 Which of the above questions is true? Since 3<5, our first question, "Is the target lower than the middle element?" is true.
Now we have a lead so let's use this to move forward.
So we have determined that our target is lower than our middle (3 < 5).
So our key point here was that the array was sorted. This means that numbers are in orders which means
that on the right side of our middle number (which is 5) all the numbers will be greater than 5.
on the left side all the numbers will be less than 5.
From the image I think we should move towards left because in that direction we can find numbers less than 5. [because our number 3 is less than 5] Now, we get a new subarray to work with, which includes all the elements to the left of 5. Let's continue the search with this new subarray.
Now our new range points are 1 and 4 which means now we have eliminated elements from 5 to 9 and will now search between 1 to 4.
Note: our middle was 5 and when we decided to search in left space our range pointers change. Whenever we reduce our search space we change pointers
When we move to left we change our right range pointer and our new right range pointer would be one less than middle. Like for above example the middle was 5 and our new right range pointer became 4.
With the new array, we repeat the same procedure: first, we find the middle element. This time, we have an even number of elements, which means there's no single definite middle number. In such cases, we can choose between the two middle elements, 2 and 3.
For explanation purpose let's select middle number 2 (Remember, how to select the middle number in general will be explained during code explanation.)
Sweet!! We found our new middle which is 2. If you remember our target is 3. Now let's think our some questions
Is the target lower than middle which means target < middle 3 < 2
Is the target greater than middle which means target > middle 3 > 2
Is the target equal to our middle which means target = middle 3 = 2
Which of the above questions is true ? As 3 > 2 our second question that is the target greater than middle is true.
Now we have a lead so let's use this to move forward.
So as we know we are at the middle number (2) and want target (3) and 3 > 2 so I think we should move right where numbers are greater than 2.
Now we get another subarray.
Now our new range points are 3 and 4 which means now we have eliminated elements from 1 to 2 and will now search between 3 to 4.
Note: our middle was 2 and when we decided to search in right space our range pointers change. Whenever we reduce our search space we change pointers
When we move to right we change our left range pointer and our new left range pointer would be one more than middle. Like for above example the middle was 2 and our new left range pointer became 3.
We repeat the same procedure. Because we have even elements this time again we have two middle elements 3 and 4 like before. Let's choose 3 as the middle element in this case.
We answer the three questions again
Is the target lower than middle which means target < middle 3 < 3
Is the target greater than middle which means target > middle 3 > 3
Is the target equal to our middle which means target = middle 3 = 3
Which of the above questions is true ? As 3 = 3 our third question that is the target = middle. Hooray!!, we found our target.
We have understood how binary search algorithm works.
Find the middle
If element found then awesome otherwise select a direction to move to
keep repeating until you find the element
If you find the element that's good otherwise you would have searched all array in that case we just return -1
Technical Definition of Binary Search
Binary search is a clever method to find a specific number in a sorted list of numbers. This technique significantly reduces the amount of time needed to find the target number by continually cutting the search space in half.
Here's how it works:
Start in the Middle: Look at the number in the middle of the list.
Compare: Is this the number you're looking for? If yes, you found it! Hooray! If no, is your number smaller or bigger than this one?
Choose a Side: If your number is smaller, ignore the right half of the list and focus on the left half. If your number is bigger, ignore the left half of the list and focus on the right half. Repeat: Keep doing this until you find your number or there are no more numbers to check.
The word "binary" means two parts. In binary search, we always split the list into two parts and choose one part to continue our search. This makes the search super quick!
Reducing the Search Space
One of the key insights of binary search is how it reduces the search space. Each time you look at the middle number and decide which half to continue searching in, you eliminate half of the remaining possibilities. This is what makes binary search so powerful.
For example, when we started we had 9 elements:
After deciding which direction to move, we eliminated the other half. That is we decided to move left, we say goodbye to numbers on the right side. This saved us to much time. We eliminated half the options in one go. That's the power of binary search
Binary Search Algorithm in Python
Let's see how we can do this in Python, a programming language that helps us talk to computers. Here's a simple way to write a binary search:
def binary_search(numbers, target):
# Initialize the left and right pointers
left = 0
right = len(numbers) - 1
# Continue the loop as long as the left pointer is less than or
equal to the right pointer
while left <= right:
# Calculate the middle index
middle = (left + right)//2
# Check if the middle element is the target
if numbers[middle] == target:
return middle # we return the index
# If the target is greater than the middle element, ignore the left half
elif numbers[middle] < target:
return left = middle + 1
# If the target is less than the middle element, ignore the right half
else:
return right = middle - 1
# If the target is not found, return -1
return -1
Define the Search: We start with the whole list of numbers. left is the first number, and right is the last number.
Loop Until Found: Keep looking while there are numbers to check.
Find the Middle Number: Look at the number in the middle.
Check the Number: If it's the one we want, we found it! If our number is bigger, ignore the left part and focus on the right. If our number is smaller, ignore the right part and focus on the left.
Repeat: Keep going until you find the number or run out of numbers to check.
Not Found: If the number isn't in the list, tell us by returning -1.
When is it a good idea to use Binary Search ?
Think of using binary search in the following conditions
We have a sorted array
We have some continuous range of numbers like 0 to 100
The data is static which means no modifications like insertion or deletions are happening
Time and Space Complexity of Binary Search
Understanding the time and space complexity of algorithms is crucial for evaluating their efficiency. Let's dive into the complexities associated with binary search.
Time Complexity
Binary search is known for its efficiency in terms of time complexity. Here's a breakdown:
Best Case: O(1)
The best-case scenario occurs when the target element is found at the first middle element check. In this case, the algorithm completes in constant time.
Average and Worst Case: O(log n)
In both average and worst-case scenarios, the time complexity of binary search is O(log n), where n is the number of elements in the array. This is because the algorithm repeatedly divides the search interval in half. Each division reduces the number of elements to be checked by half, resulting in a logarithmic time complexity.
The logarithmic nature of binary search makes it highly efficient for large data sets. For example, with an array of 1,000,000 elements, binary search would take at most about 20 comparisons (log2(1,000,000) ≈ 20).
Space Complexity
The space complexity of binary search is also an important aspect to consider:
Iterative Implementation: O(1)
When implemented iteratively, binary search requires a constant amount of additional space, O(1), for the left, right, and middle pointers. This is because it doesn't need any extra space that grows with the input size.
Recursive Implementation: O(log n)
If binary search is implemented using recursion, the space complexity increases to O(log n). This is due to the additional space required for the function call stack. Each recursive call adds a new frame to the stack, which in the worst case would be the height of the binary search tree (log n).
Summary
Time Complexity: Best Case O(1), Average/Worst Case O(log n)
Space Complexity: O(1) for iterative implementation, O(log n) for recursive implementation
The combination of low time and space complexity makes binary search an excellent choice for searching in sorted arrays, especially when dealing with large data sets.
Conclusion
Using binary search algorithm in python is like a magical way to find things quickly. By dividing the search area in half each time, you can find what you're looking for in no time. Now you know a cool trick that makes searching fun and easy!
Happy searching!
Comments