Edisi pembelajaran bahasa Indonesia. Kode dan keluarannya tetap seperti aslinya.

Pencarian biner pada array terurut

Temukan indeks target dalam waktu logaritmik atau laporkan bahwa target tidak ada.

Baca N dan target K, lalu N integer dalam urutan tidak menurun. Fungsi binary_search harus mengembalikan indeks berbasis nol jika ditemukan atau -1 jika K tidak ada.

Hitung mid = low + (high - low) / 2 dan keluarkan bagian yang tidak mungkin memuat target. Pertahankan label bahasa Inggris Found at index: dan Not found: -1.

Masukan

Baris pertama: N dan K. Baris kedua: N integer terurut yang dipisahkan spasi.

Keluaran

Found at index: <indeks> atau Not found: -1

Batasan

1 <= N <= 100.000
-1.000.000.000 <= arr[i], K <= 1.000.000.000
Array terurut dalam urutan tidak menurun.
Pencarian: waktu O(log N) dan ruang tambahan O(1).

Petunjuk

Mulai dengan low = 0 dan high = n - 1; lanjutkan selama low <= high.
Keluarkan titik tengah: high = mid - 1 atau low = mid + 1.

Kode C

#include <stdio.h>

// Function to perform binary search
// Returns 0-based index of target if found, else -1
int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    // TODO: Implement O(log N) binary search loop
    // Tip: Use mid = low + (high - low) / 2 to prevent integer overflow

    return -1; // Target not found
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

Buka di kompiler

Solusi dan penjelasan

Jika arr[mid] cocok, kembalikan mid. Target yang lebih kecil hanya mungkin di kiri, sedangkan target lebih besar hanya mungkin di kanan.

Setiap langkah mengurangi rentang sekitar setengahnya. Jika batas berpapasan, target tidak ada. Uji elemen tepi dan nilai yang tidak ditemukan.

Pencariannya memerlukan O(log N), tetapi membaca N bilangan masukan memerlukan O(N). Untuk duplikat, hasilnya satu kemunculan dan belum tentu yang pertama.

Kode solusi

#include <stdio.h>

int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        // Overflow-safe midpoint calculation
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

Pertanyaan umum

Mengapa kode dan keluarannya tetap dalam bahasa Inggris?

Kata kunci, pengenal, dan teks yang diperiksa tes dipertahankan agar program tidak berubah. Penjelasan dan kontrol telah diterjemahkan.