Binary search is a search algorithm that works efficiently with a sorted list or array. It searches for a particular element by repeatedly dividing the search interval in half, until the target element is found or the search interval is empty.
Here’s an example of binary search:
Suppose you have a sorted array of numbers: [4, 8, 12, 16, 20, 24, 28, 32, 36, 40]
You want to find if the number 20 is in the array.
The general steps for binary search algorithm are:
Using binary search, you can start with checking the middle element of the sorted list, which is 20 in this case. Since the target value matches the middle element, the search is successful, and we return the index of the middle element, which is 4.
So, in this example, we were able to find the target value using only three comparisons, as compared to a linear search which would have taken 6 comparisons on an average to find the target value.
Binary search requires a sorted list of elements.
It starts by dividing the list into two equal parts to find the midpoint.
It compares the value in the midpoint with the target value and decides which half to discard.
If the value in the midpoint is less than the target value, the left half of the list is discarded, and the search proceeds on the right half.
If the value in the midpoint is greater than the target value, the right half of the list is discarded, and the search proceeds on the left half.
This process is repeated until the target value is found, or until the search area is reduced to an empty set.
Binary search runs in O(log n) time, which is faster than linear search, especially for large datasets.
It is a useful algorithm for searching a specific element in a large sorted list efficiently.
Binary search is not suitable for unsorted or partially sorted lists.
Binary search is more efficient than linear search in terms of the number of comparisons required to find the target value.
What is the time complexity of Binary Search when searching for an element in a sorted array of size n?
Answer: O(log(n))
What is the main advantage of using Binary Search over Linear Search for finding elements in an array?
Answer: Binary Search has a faster average search time, which is O(log(n)) instead of O(n) for Linear Search.
Can Binary Search be used on unsorted arrays?
Answer: No, Binary Search requires the array to be sorted in order to work correctly.
What is the worst-case scenario for Binary Search when searching for an element that does not exist in the array?
Answer: The worst-case scenario is when the target element is not in the array at all, and Binary Search must check every element. This takes O(log(n)) time, just like when the element is found.
How does Binary Search work internally to find a target element in a sorted array?
Answer: Binary Search continually narrows down the search range by comparing the target element to the middle element of the current range. If the target is less than the middle element, the search range is narrowed to the lower half of the current range. If the target is greater, the search range is narrowed to the upper half. This process is repeated until either the target element is found or the search range is empty.