DSA7# Binary Search
Binary Search is a search algorithm used in a sorted array. It can be implemented in two ways which are iterative or recursive methods.
The binarySearch function receives four parameters: the array, the value we are looking for
x, and the array's first
lowand last position
We will traverse the array while
lowis less or equal to
highbecause they are supposed to be at the two extremities, if
lowis greater than
highwe assume that we have already traversed the part of the array that is interesting and if we don’t find the value we return -1.
To avoid traversing the entire array since it is already sorted, the binary search algorithm calculates the middle of the array and checks if the value that is in the middle is equal to
x, if so we return the position. if it isn’t we check which part of the array is worth looking at by calculating if the value in the middle is greater or less than
if the middle value is greater than
x, the case before it becomes the new
high, and if it is less than
xthe case just after it becomes the new
low. That means the interval will be reduced until we find x. If x isn’t in the array we return -1 because at one moment
lowwill be greater than
highand the traversal will be stopped.
The value we are looking for is 4.
Firstly we calculate the middle of the array which is 3. array is 6 which is less than 4 the value we are looking for, so we reduce the interval the case before 3 becomes the new high.
In the second pass in the loop, we calculate again the middle which is equal to 2. array is to 4, which means we found our x and then return 2.
Complexity analysis: Since we will never traverse the entire array, the binary search algorithm has a time complexity of O(log n) and because we don’t use any extra space the space complexity is O(1).
We are at the end of our post, we can summarize that binary search is an algorithm that can help to find a value in a sorted array with a time complexity of O(log n), I hope that you learn something new by reading this article.
The Nothing 🔺