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.

Javascript iterative method

Javascript recursive method

Explanation

The binarySearch function receives four parameters: the array, the value we are looking for x, and the array's first lowand last position high.

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 x.

if the middle value is greater thanx, 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.

Illustration

The value we are looking for is 4.

Firstly we calculate the middle of the array which is 3. array[3] 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[2] 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).

Conclusion:

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 🔺