Start learning free

LESSON 397 OF 675 · DIVIDE AND CONQUER

Binary Search

Practice Recursive

Implement a recursive Binary Search algorithm that given a sorted array of integers nums, finds and returns the index of a given value.

If the value doesn't exist in nums, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: the element at index 2 is 4

Note:

Your algorithm should run in O(log n) time and use O(log n) extra space.

Hints:

Since our subproblems reduce to searching the value in a subarray, we will write a recursive helper function which takes nums, the bounds left and right and value, looks for value in the part of nums between indexes left and right (both included) and returns its index or -1 if not found.

Inside the function, we should compute the middle index mid and compare the element at mid to value. What should we do if:
  • the element at mid is equal to value?
  • the element at mid is less than value?
  • the element at mid is greater than value?

  • If the element at mid is equal to value, then we found our solution and we should return mid
  • If the element at mid is less than value, we should continue the search between indexes mid + 1 and right, i.e. return the result of the recursive call on that range
  • If the element at mid is greater than value, we should continue the search between indexes left and mid - 1, i.e. return the result of the recursive call on that range
When should the function return -1 tho?

At the start of the function, we should treat the base case: left > right. This means we reduced the searching area to an empty subarray, so there is no solution and we should return -1
STEP 1 OF 7
    Ctrl + Enter to check