แบบฝึกหัด 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));
}

สร้างปุ่ม Run สำหรับตัวอย่างนี้ ผลลัพธ์จากการรันโค้ด

Some(5)
None

ฝึกฝน

เปิดตัวอย่างในคอมไพเลอร์ออนไลน์ ลองเปลี่ยนค่าหรือเพิ่มบรรทัด แล้วทายผลลัพธ์ก่อนกดรัน จากนั้นลองทำให้โค้ดผิดโดยตั้งใจ แล้วอ่านข้อความจากคอมไพเลอร์

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: Structs →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด