Binary search is a quick search algorithm with an O run-time complexity (log n). This search algorithm operates on the divide and conquers principle. The data collection should be sorted for this algorithm to perform properly.
Binary search looks for a certain item by comparing the collection’s middlemost item. If a match is found, the item’s index is returned. If the item is greater than the middle item, the item is looked for in the sub-array to the left of the middle item. Otherwise, the item is sought in the sub-array to the right of the center item. This method is repeated on the sub-array until the size of the sub-array is reduced to zero.
The pseudocode of binary search algorithms should look like this −
Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound - lowerBound ) / 2 if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x set upperBound = midPoint - 1 if A[midPoint] = x EXIT: x found at location midPoint end while end procedure