Binary Search | A Level | By ZAK
Understanding of linear and binary searching methods.
Algorithm to implement a binary search.
The conditions necessary for the use of a binary search.
How the performance of a binary search varies according to the number of data items?
Understanding Linear and Binary Search
Linear Search:
Linear search is a straightforward search method where each element in an array or list is checked sequentially until the desired element is found or the list is exhausted. It doesn't require the list to be sorted and is easy to implement. The main disadvantage of linear search is its inefficiency on large lists, as it might have to examine every single element in the worst case.
Binary Search:
Binary search is a much more efficient algorithm but requires the array or list to be sorted beforehand. It operates on the principle of divide and conquer by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half, or if the value is greater, it continues in the upper half. This process repeats until the value is found or the interval is empty.
Algorithm for Binary Search
Here's a step-by-step algorithm to implement binary search:
1. Start with Two Pointers: Initialize two pointers, low at the start of the array and high at the end of the array.
2. Check the Middle Element: Find the middle element. If the middle element is equal to the key, return the index.
3. Adjust the Range: If the key is smaller than the middle element, set high to mid - 1. If the key is larger, set low to mid + 1.
4. Repeat or Exit: Repeat the process until low is greater than high or the key is found. If the key is not found by the end of the loop, the key is not in the array.
Here is a simple code in Python to implement binary search:
python code for binary search
def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low less or equal high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] greater key:
high = mid - 1
else:
low = mid + 1
return -1 # Element not found
Conditions Necessary for Binary Search
Sorted Array: The most crucial condition for binary search is that the array must be sorted in order for the algorithm to function correctly.
Performance of Binary Search According to the Number of Data Items
The performance of binary search is generally much better than that of linear search, especially as the size of the data set increases. The time complexity of binary search is O(log n), where n is the number of elements in the array. This logarithmic performance means that doubling the size of the dataset results in just one extra comparison in the worst case. This makes binary search highly efficient for large datasets compared to linear search, which has a time complexity of O(n).
Overall, binary search is an excellent choice when dealing with large, sorted datasets where quick search times are necessary.
--ZAK