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

Try the guessing game below, it will always guess your number within 7 turns

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:

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store