Binary search is one of the fundamental algorithms in computer science. A binary search, also known is a search algorithm finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.
Binary search runs in at worst logarithmic time, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. Although specialized data structures designed for fast searching such as hash tables can be searched more efficiently, binary search applies to a wider range of problems.
lo = 1, hi = size(A)
while lo <= hi:
mid = lo + (hi-lo)/2
if A[mid] == target:
else if A[mid] < target:
lo = mid+1
hi = mid-1
// target was not found
Binary Search THETA(log n)
T(n) = T(n/2) + THETA(1)
Number guessing game
Let’s look at the guessing game as an example of using binary search, a Divide and Conquer Algorithm by halving our possible number of guesses. To play the guessing game, a person (player A) will choose a random number from n to m, another person (player B) will have to guess player A’s number in “x” turns. Player A will assist player B by telling player B if the number they guessed is higher than or lower than player A’s randomly chosen number. The Algorithm will tell you if it is possible to guess player A’s number in the given amount of turns x, and will tell the maximum amount of tries or guesses you will need in order to guess there number correctly. The Number Guessing Game uses binary search to quickly find a solution. A binary search is a dichotomic divide and conquer search algorithm. The maximum number of turns it takes to guess a number from 1 to 100 is log2(100 -1 +1)= log2(100) = 7. Hence the worst case running time is log2(Max — Min + 1).
Try the guessing game below, it will always guess your number within 7 turns
The algorithm used to make this game, uses a divide and conquer approach by halving the possible choices/guesses !
Instructions to play:
1) Think of a number in your head from 1 to 100
2) The program will start off by guessing if your number is 50
3) You must tell the program if it’s guess was lower or higher than the number you thought of in your head in step 1, if it guessed it right click correct
4) If the computer didn’t guess your number continue with steps 2–4, else go to step 5
5) The program should have guessed your number within 7 turns. Click Refresh to play again
Link To The Guessing you Can Play
Number Guessing Game Program
Get the code here:
Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )
Check Out the following for content / videos on Algorithm Analysis and Programming:
Video Tutorials on Recurrence Relation:
Video Tutorial on Algorithm Analysis: