(This question has been seen in the interviews of the following companies: AOneCode, Facebook, Google, Airbnb)
This is our Online Judge Demo. Please try it out.
In computer science, binary search is a search algorithm that 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 not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half. Again take the middle element to compare with the target value, and repeat this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
arr = [1, 2, 4], target = 2
Return the index of the target value.
arr = [1, 2, 4], target = 0
Return -1 if the target value not exist in the array.