Binary Search

Try it yourself. The solutions are at the top of the page.

Iterative solution

1. Declare two pointers. start = 0 and end = nums.length - 1
2. Run a loop with start <= end condition.
3. Declare a median variable - mid which will be equal to let mid = Math.floor((start + end) / 2);
4. if mid is EQUAL to target, that means the target is found in the given array, return the current index.
5. if mid is GREATER than target, that means the target element must be present in the left part of the array, i.e. from start to mid - 1 length.
6. if mid is LESS than target, that means the target element must be present in the right part of the array, i.e. from mid + 1 to end.
7. Return false if code exits from the while loop without returning anything.

Recursive solution

1. Following the same iterative paradign, create two variables start = 0 and end = arr.length - 1.
2. Create a helper function binarySearchHelper() that takes start, end, mid = start + end / 2 and nums array.
3. The breaking case is when start > end. that means the two pointers overlap.
4. if target === arr[mid] - means we found the target, return mid element.
5. if arr[mid] < target - recurse the binarySearchHelper() method with start = mid + 1 condition, because if the target is present in the array, it will definitely be in the right sub array.
6. if arr[mid] > target - recurse the binarySearchHelper() method with end = mid - 1 condition, because if the target is present in the array, it will definitely be in the left sub array.