Problem overview
The method find receives a sorted array of integers, nums, and a value. It returns the index where value sits, or -1 when the array doesn't contain it. The search has to be recursive, with O(log n) time and O(log n) extra space.
In the example, nums = [1, 2, 4, 5] and value = 4. The 4 is at index 2, so the answer is 2. With value = 3 the answer would be -1, because 3 is not in the array.
Approach: halve the range with every call
Scanning the array from the left works, but it costs O(n). Sorting gives something better: look at the middle element. If it equals the value, you are done. If it is smaller than the value, everything at or left of the middle is smaller too, so the value can only be in the right half. If it is larger, only the left half remains. One comparison discards half of the candidates, and halving n repeatedly takes about log₂ n steps.
The recursion needs to say which part of the array it is searching. Copying a half into a new array would cost time, so the helper keeps the same array and passes two bounds, left and right, that mark the inclusive range still in play. An empty range (left > right) means there is nowhere left to look, which is the base case.
A simple trace for [1, 2, 4, 5] and value = 4: the first call has left = 0, right = 3, so mid = 1 and nums[1] is 2. That is smaller than 4, so the search continues with left = 2. Now mid = (2 + 3) / 2 = 2 and nums[2] is 4, so the call returns 2.
Step by step
- Delegate from
find. It calls the helperbinarySearchon the whole array, from index 0 tonums.count - 1, and returns whatever the helper returns. - Declare the helper above
findwith parameters for the array,left,rightand the value. The underscores mean callers pass the arguments without labels. - Handle the empty range. When
left > right, return-1. Without this base case the recursion would never stop. - Compute
midas(left + right) / 2. Integer division drops the fraction. - Return
midon a match. Checking equality first leaves two cases for the rest of the method. - Value larger than
nums[mid]: searchmid + 1torightand return that call's result. - Otherwise: search
lefttomid - 1and return that result.
The solution in Swift
class Solution {
func binarySearch(_ nums: [Int], _ left: Int, _ right: Int, _ value: Int) -> Int {
if left > right {
return -1
}
let mid = (left + right) / 2
if nums[mid] == value {
return mid
}
if nums[mid] < value {
return binarySearch(nums, mid + 1, right, value)
} else {
return binarySearch(nums, left, mid - 1, value)
}
}
func find(_ nums: [Int], _ value: Int) -> Int {
return binarySearch(nums, 0, nums.count - 1, value)
}
}
The Swift details worth a closer look:
- Unlabeled parameters. Swift normally requires argument labels at the call site. Writing
_before a parameter name removes the label, so the call readsbinarySearch(nums, 0, nums.count - 1, value). - Arrays are values, but passing one is cheap.
[Int]is a value type, yet Swift copies its storage only when someone modifies it. The helper never writes tonums, so all the recursive calls share one buffer and no copy happens. - Every branch returns. A Swift function with a return type must return a value on every path, or the compiler reports an error. That is why the recursive calls are written as
return binarySearch(...). - Integer division.
/on twoIntvalues truncates toward zero. Hereleft + rightis never negative inside the search, so(left + right) / 2is the floor of the average and always a valid index between the bounds. - Overflow traps. An
Intis 64 bits, and overflowing it stops the program instead of wrapping. Adding two array indices can't get anywhere near that limit, so(left + right) / 2is safe here.
Complexity
Time: O(log n). Each call does a constant amount of work and passes on a range at most half as long, since the element at mid is excluded. A range of n elements shrinks to empty after about log₂ n calls.
Space: O(log n). The array is shared, not copied. The extra memory is the call stack: one frame for each recursive call that hasn't returned, and there are at most about log₂ n of them.
Edge cases and common mistakes
- Empty array.
nums.count - 1is-1, so the first call hasleft = 0andright = -1. It hits the base case at once and returns-1. - Single element. With
[7]and value 7, the range holds one index andmidis 0, so the answer is 0. With another value, the next call gets an empty range and returns-1. - First and last positions. In
[1, 2, 4, 5], the value 1 gives 0 and the value 5 gives 3. - Duplicates. The method returns some index holding the value, not necessarily the first one. For
[2, 2, 2, 2]and value 2 it returns 1. midinstead ofmid - 1ormid + 1. If a recursive call keepsmidin its range, a range with one element is searched again and again, and the recursion never ends.- Forgetting to return the recursive result. The index found deep in the recursion has to travel back up through every caller.
- Unsorted input. Binary search relies on the order. On an unsorted array it can miss a value that is present.
Testing
nums = [1, 2, 4, 5],value = 4gives2.nums = [1, 2, 4, 5],value = 3gives-1.nums = [],value = 3gives-1.nums = [7],value = 7gives0.nums = [1, 2, 4, 5], values1and5give0and3.
