LeetCode Entry

33. Search in Rotated Sorted Array

22.05.2026 medium 2026 kotlin rust

Binary search in shifted array

33. Search in Rotated Sorted Array medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1367

Problem TLDR

Binary search in shifted array

Intuition

• find the split point
• binary search in two parts

Approach

• insertion point: the first value is less than first part and bigger than second part
• if target is less than first value - it is in the second part

Complexity

• Time complexity: \(O(logn)\)

• Space complexity: \(O(1)\)

Code

    fun search(n: IntArray, t: Int) = n.asList().run {
        val s = binarySearch { if(it < n[0])1 else -1}.inv()
        maxOf(-1, binarySearch(t, 0, s), binarySearch(t, s))
    }

    pub fn search(n: Vec<i32>, t: i32) -> i32 {
        let (s,b) = (n.partition_point(|&x| x >= n[0]), (t<n[0]) as usize);
        [&n[..s],&n[s..]][b].binary_search(&t).map_or(-1, |i|(i+s*b)as _)
    }