Day 19 - Search in Rotated Sorted Array

Solution.kt

// https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/530/week-3/3304/

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        return bs(nums, target, 0, nums.size - 1)
    }
    
    fun bs(nums: IntArray, target: Int, a: Int, b: Int): Int {
        if (a > b) {
            return -1
        }
        
        val m = ((a + b) / 2).toInt()
        
        if (nums[m] == target) {
            return m
        }
        
        if (nums[m] >= nums[a]) {
            if (target >= nums[a] && target < nums[m]) {
                return bs(nums, target, a, m - 1)
            } else {
                return bs(nums, target, m + 1, b)    
            }
        } else {
            if (target <= nums[b] && target > nums[m]) {
                return bs(nums, target, m + 1, b)
            } else {
                return bs(nums, target, a, m - 1)
            }
        }
    }
}

Yeah, you are right, my first solution was lineal. I sometimes get confused about this algorithm, I tend to compare this with other divide and conquer algorithms, for example the merge sort is linearitmic because it does n operations in log(n) recursive calls so I thought that by doing log(n) recursive calls my algorithm was logaritmic.

I have updated my solution, now I am discarding a half on each iteration. Thanks for the comment.