What is Binary Search ?
Binary Search is searching technique which works on Divide and Conquer approach. It used to search any element in a sorted array.
As compared to linear, binary search is much faster with Time Complexity of O(logN) whereas linear search algorithm works in O(N) time complexity.
Binary Search Step-By-Step Process Breakdown:
In this step-by-step process, we’re going to be breaking down how to do a Binary Search on the below given array.”
Target to find: 59
- We are going to need to keep track of the 3 following things as variables to perform a Binary Search: startIndexPosition, middleIndexPosition, and endIndexPosition.
- startIndexPosition will always be 0:
let stastartIndexPositionrtIndex = 0
- endIndexPosition can be calculated using
- We want to get an inital
endIndexPosition, and the divide by 2. We can use
Math.floor()to round down or
Math.ceil()to round up.
- We will use while loop in order to iterate the process
- If the
middleIndexPositionvalue is less than the target value of 59, we know that our target value will be somewhere to the right of the middleIndexPosition. We can then assign our startIndexPosition variable as the current middleIndexPosition value, ignoring the left half of the array. We should also increment middleIndexPosition by the count of 1 if our target number “59” >
- If the
middleIndexPositionvalue is greater than the target value, 59, we know that our target value will be in to the left of the middleIndexPosition. We can then assign our endIndex variable as the current middleIndex value, ignoring the right half of the array. We should also Decrement middleIndexPosition by the count of 1 if our target number “59” <
- If the
middleIndexPositionvalue is equal to the target value of 59, we have found our target number “59.”, target is found :)
- Hurray we got it done