LESSON 259 OF 348 · DIVIDE AND CONQUER

Binary Search in Scala

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: nums[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 function binarySearch(nums, left, right) which looks for value in nums[left...right] and returns its index or -1 if not found.

Inside the function, we should compute the middle index mid and compare nums[mid] to value. What should we do if:

a[mid] is equal to value?
a[mid] is less than value?
a[mid] is greater than value?

If a[mid] is equal to value, then we found our solution and we should return mid
If a[mid] is less than value, we should continue the search in nums[mid + 1...right], e.g. return binarySearch(nums, mid + 1, right)
If a[mid] is greater than value, we should continue the search in nums[left...mid - 1], e.g. return binarySearch(nums, left, mid - 1)

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

Guided

Ctrl + Enter to check