Binary Search is a way to efficiently search an array of items by halving the search space each time.
An example that demonstrates Binary Search:
Write a function that returns either the location of the target value in the array, or -1 if the array does not contain the target value.
- Let min = 0 and max = n
- If max < min, then stop: target is not present in the array. Return -1.
- Guess the average of max and min, rounded down so that it is an integer
- If you guessed the number, stop. You found it!
- If the guess was too low, set min to the one larger than the guess.
- If the guess was too high, set max to the one smaller than the guess.
- Go back to step 2. (while loop — don’t use “for” loop because the binary search doesn’t guess the indices by sequential order. )
My solution in Ruby:
Running the code yields the expected outputs: