Binary Search:
Definition:
Binary searches are effective algorithms based on the principle of "divide and conquer," which enhances the search by repeatedly splitting the array in half until you either locate the element or the list is reduced to one piece that doesn't match the required element.
Time Complexity:
1. Best Case:
- The element being search could be found in the first position.
- In this case, the search ends with a single successful comparison.
- Thus, the best-case for binary search algorithm is O(1).
2. Average Case:
- When the element searched is in the middle of the array/list, the average case of the binary search algorithm is O(log n).
3. Worst Case:
- The element being searched may be at the last position in the array/list or not at all. For both of which the search will continue until the end.
- Thus, in the worst-case scenario of the binary search algorithm is O(log n).
Space Complexity:
- The binary search algorithm takes up no extra space; its space complexity is O(1) for an array of n elements.
Application of Binary Search Algorithm:
- Dictionary: A dictionary contains thousands of words. It's time consuming to go through and check for each word if we want to search a specific word. Thus, we use binary search to make the searching a lot faster.
- Debugging a linear piece of code: If a code has many steps mostly executed in a sequence and there's a bug, we can isolate the bug by finding the earliest step where the code produces results which are different from the expected ones. Of course, it saves time.
- Figuring out resource requirements for a large system:
- Binary search can be used to find numerical solutions to an equation.
Binary Search Algorithm:
Step-1: Begin with the mid element of the whole array as a search key.
Step-2: If the value of the search key is equal to the item, then return an index of the search key.
Step-3: If the value of the search key is less than the item then narrow down the interval to the lower half.
Step-4: Otherwise, narrow it to the upper half.
Step-5: Repeatedly check from the Step-2 until the value is found or the interval is empty.
Example in JavaScript:
Why Binary search is efficient over linear search?
A Linear Search method might become quite time-consuming if we needed to identify a number out of, say, 1,000,000 numbers and that number was in the last spot. It will take 1,000,000 iterations for linear search to find the value. Whereas for binary search, it will take about 19 iterations.
Binary Search Algorithm Advantages:
- It eliminates half of the list from further searching by using the result of each comparison.
- It indicates whether the element being searched is before or after the current position in the list.
- This information is used to narrow the search.
- For large lists of data, it works significantly better than linear search.
Binary Search Algorithm Disadvantages:
- The array/list must be sorted.
- Small and unsorted arrays would take considerate time in sorting and then searching the desired element. So, binary search is not preferred in such cases.
- Programming binary search algorithm is error prone and difficult.