080_search_rotated.sio

//@ run-pass
// HumanEval 080: Search in Rotated Sorted Array
//
// Search for a target in a sorted array that has been rotated at some pivot.
// For example, [4,5,6,7,0,1,2] is [0,1,2,4,5,6,7] rotated at pivot 4.
// Uses modified binary search in O(log n). Returns the index or -1 if not found.

fn search_rotated(arr: [i64; 256], n: i64, target: i64) -> i64 with Mut, Panic {
    var lo: i64 = 0
    var hi: i64 = n - 1

    while lo <= hi {
        let mid = lo + (hi - lo) / 2
        if arr[mid] == target {
            return mid
        }

        // Determine which half is sorted
        if arr[lo] <= arr[mid] {
            // Left half is sorted
            if target >= arr[lo] && target < arr[mid] {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        } else {
            // Right half is sorted
            if target > arr[mid] && target <= arr[hi] {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
    }

    0 - 1
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [4, 5, 6, 7, 0, 1, 2], target=0 -> index 4
    var a1: [i64; 256] = [0; 256]
    a1[0] = 4
    a1[1] = 5
    a1[2] = 6
    a1[3] = 7
    a1[4] = 0
    a1[5] = 1
    a1[6] = 2
    assert(search_rotated(a1, 7, 0) == 4)

    // Test 2: [4, 5, 6, 7, 0, 1, 2], target=3 -> -1
    assert(search_rotated(a1, 7, 3) == 0 - 1)

    // Test 3: [4, 5, 6, 7, 0, 1, 2], target=5 -> 1
    assert(search_rotated(a1, 7, 5) == 1)

    // Test 4: not rotated [1, 2, 3, 4, 5], target=3 -> 2
    var a4: [i64; 256] = [0; 256]
    a4[0] = 1
    a4[1] = 2
    a4[2] = 3
    a4[3] = 4
    a4[4] = 5
    assert(search_rotated(a4, 5, 3) == 2)

    // Test 5: single element [1], target=1 -> 0
    var a5: [i64; 256] = [0; 256]
    a5[0] = 1
    assert(search_rotated(a5, 1, 1) == 0)

    // Test 6: single element [1], target=0 -> -1
    assert(search_rotated(a5, 1, 0) == 0 - 1)

    // Test 7: [2, 1], target=1 -> 1
    var a7: [i64; 256] = [0; 256]
    a7[0] = 2
    a7[1] = 1
    assert(search_rotated(a7, 2, 1) == 1)

    // Test 8: find first element
    assert(search_rotated(a1, 7, 4) == 0)

    // Test 9: find last element
    assert(search_rotated(a1, 7, 2) == 6)

    println("080_search_rotated: ALL TESTS PASSED")
    0
}