Binary Search

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.

binary_search(A, target):
lo = 1, hi = size(A)
while lo <= hi:
mid = lo + (hi-lo)/2
if A[mid] == target:
return mid
else if A[mid] < target:
lo = mid+1
else:
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
http://everythingcomputerscience.com/GuessingGame/GuessingGame.html

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:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything