Close

# Mohit Athwani

MA

This is straight up Binary Search problem with some modifications. When we find the mid point of the given array, one of two things will hold true:

1. The array from `start` to `mid` is sorted.
2. The array from `mid` to `end` is sorted.

Once we know which is the sorted half, all we have to do is check if the search target lies within the sorted half. If yes, do regular binary search in that half of the problem. If no, then we have to update the 3 pointers depending on whether the lower half is sorted or upper half is sorted and than recurse again.

Let’s look at an example. In the array `nums = [4, 5, 6, 7, 8, 0, 1, 2]`, and `target = 6`, `start = 0`, `end = 7` and `mid = 3`. `nums[start...mid]` is sorted, i.e. `4, 5, 6, 7` are in sorted order and `8, 0, 1, 2` are not sorted.

We check if `6` lies between `nums[start]` and `nums[mid]`. Since it does, we do a binary search from indices `start` to `mid - 1`.

Let’s set the target as `1`. `1` appears in the unsorted half of the array. We will now recursively find the sorted and unsorted halves of the upper half of the array. Now, `start = 4`, `end = 7` and `mid = 5`. `nums[6...7]` is sorted in this case so we perform binary search in this section of the array.

The code for this is pretty straight forward:

```func search(_ nums: [Int], _ target: Int) -> Int {
guard nums.count > 0 else {
return -1
}

var start = 0
var end = nums.count - 1

func search(start: Int, end: Int) -> Int {

if end < start {
return -1
}

let mid = start + (end - start) / 2

print(start, mid, end)

if nums[mid] == target {
return mid
}

//lower half is sorted
if nums[start] <= nums[mid] {
if target >= nums[start] && target <= nums[mid] {
//search in lower half
return search(start: start, end: mid - 1)
} else {
//search in upper half
return search(start: mid + 1, end: end)
}
}

//upper half is sorted
if nums[mid] < nums[end] {
if target >= nums[mid] && target <= nums[end] {
//search in upper half
return search(start: mid + 1, end: end)
} else {
//search in lower half
return search(start: start, end: mid - 1)
}

}

return -1
}

return search(start: 0, end: nums.count - 1)
}```

Since this is straight up binary search, the time complexity will be `O(lg N`) and since this is recursive, I would say that this is `O(lg N)` space as well. If we refactor the code and pass the value of mid to the nested `search(start:end:)` function instead of calculating it in the function, we can make the recursive call tail recursive and in that way there will be no extra space if the compiler can make those optimizations.

Problem taken from Leetcode.

Code hosted on Github.