LeetCode Entry

153. Find Minimum in Rotated Sorted Array

15.05.2026 medium 2026 kotlin rust

Binary search in shifted array

153. Find Minimum in Rotated Sorted Array medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1360

Problem TLDR

Binary search in shifted array

Intuition

    // 5 6 7 0 1 2 3 4
    // l     m       h
    // 6 7 0 1 2 3 4 5
    // l     m       h
    // 6 7 0 1 2 3 4 5
    // l m   h

    // 4 5 6 7 0 1 2
    // l     m     h
    //         l

• invent the binary search from scratch
• or notice that we can compare all elements with last

Approach

• use built-in functions, Rust: partition_point, Kotlin: binarySearch {..}

Complexity

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

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

Code

    fun findMin(n: IntArray) =
        n[-1-n.asList().binarySearch { if (it > n.last()) -1 else 1}]

    pub fn find_min(n: Vec<i32>) -> i32 {
        n[n.partition_point(|&x|x>n[n.len()-1])]
    }