Binary Search Implementation

Hello today , I will show you an implementation of binary search I have constructed using the Hack programming language. Binary search is a very efficient searching procedure in which we have comparisons from the middle and will either go to the left of the middle, the right , or we are the middle and therefore we stop. By using binary search eliminate nearly half the elements in the first pass.

 

In this implementation I created an object of the Vector class provided in Hack.

Code for Hack binary search

First we compute the middle index then check if we are the value at the middle index. Note: During all the comparisons I realized that Hack will only accept integers as index values. To overcome this I casted the middle to an integer for each of these comparisons.

If it is not the middle then it will perform binary search on the left side of the vector. Next we perform binary search on  the right side of the vector. We do this until we find our value and return mid or we the element fails to exist in the vector and we return -1.

Our binary search program outputs letting us know that the integer 5 is located at index 3