Find the index of the large integer

Array Binary Search Interactive

56.5% acceptance

Mar 31, 2026

263

// This is the ArrayReader's API interface. // You should not implement it, or speculate about its implementation struct ArrayReader; impl Array Reader { pub fn compareSub(l: i32, r: i32, x: i32, y: i32) -> i32 {} // Compares the sum of arr[l..r] with the sum of arr[x..y] // return 1 if sum(arr[l..r]) > sum(arr[x..y]) // return 0 if sum(arr[l..r]) == sum(arr[x..y]) // return -1 if sum(arr[l..r]) < sum(arr[x..y]) // Returns the length of the array }

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn get_index(reader: &ArrayReader) -> i32 {
    let mut left = 0;
    let mut right = reader.length() - 1;

    while left < right {
      let mid = left + (right - left) / 2;
      let len = right - left + 1;

      if len % 2 == 0 {
        if reader.compareSub(left, mid, mid + 1, right) > 0 {
          right = mid;
        } else {
          left = mid + 1;
        }
      } else {
        match reader.compareSub(left, mid - 1, mid + 1, right) {
          0 => return mid,
          1 => right = mid - 1,
          _ => left = mid + 1,
        }
      }
    }

    left
  }
}