Упражнения по Rust

Binary Search in Rust

Find a value in a sorted slice by halving the search range at every step.

Начальный
Чтение: 3 мин
Примеров для запуска: 1

Что вы узнаете

low, high and middle
Returning Option<usize>
Why it is fast

Запустить код →

Search for 23

164

235

386

567

Found at index 5 after three steps.

Halve the range each step

Binary search looks at the middle of a sorted list and throws away the half that cannot contain the target. Each step halves the work, so it is very fast on large lists.

low and high mark the part that is still being searched. The function returns Some(index) when the target is found and None when the range becomes empty. low + (high - low) / 2 finds the middle without overflow.

Главное

The list must be sorted.
Each step throws away half.
None means the value is not there.

Пример на Rust, который можно запустить

Rust

Запустить код →

main.rs

fn binary_search(items: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = items.len();
    while low < high {
        let middle = low + (high - low) / 2;
        if items[middle] == target {
            return Some(middle);
        } else if items[middle] < target {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    None
}

fn main() {
    let sorted = [2, 5, 8, 12, 16, 23, 38, 56];
    println!("{:?}", binary_search(&sorted, 23));
    println!("{:?}", binary_search(&sorted, 7));
}

Получить кнопку запуска для этого примера Результат выполнения

Some(5)
None

Практика

Откройте пример в онлайн-компиляторе, измените значение или добавьте строку и попробуйте предсказать вывод до запуска. Затем намеренно сломайте код и прочитайте сообщение компилятора.

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Далее: Structs →

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи