KAL
Menu

SEARCH dan SEARCH ALL

Pencarian tabel secara serial dengan SEARCH dan biner dengan SEARCH ALL beserta syaratnya.

Daftar isi

Verb SEARCH dan SEARCH ALL mencari satu elemen tabel yang memenuhi syarat, lalu meninggalkan register indeks tabelnya pada posisi temuan itu. Topik ini membahas SEARCH yang menelusuri tabel secara serial dari posisi indeks semula, SEARCH ALL yang membagi tabel terurut menjadi dua bagian pada setiap langkah, syarat deklarasi yang wajib dipenuhi masing-masing verb, dan penanganan keadaan tidak ditemukan. Dua program utuh memperagakan keadaan ditemukan maupun tidak ditemukan pada tabel berisi tujuh entri.

SEARCH untuk pencarian serial#

SEARCH menelusuri elemen tabel satu per satu, sehingga setiap tabel sasarannya wajib memiliki register indeks yang dideklarasikan melalui INDEXED BY. Pencarian dimulai dari nilai indeks saat itu, menguji kondisi WHEN berurutan pada setiap elemen, lalu menaikkan indeks dan berpindah elemen apabila tidak ada kondisi yang terpenuhi. Badan AT END dieksekusi ketika tabel habis tanpa temuan, sedangkan badan WHEN yang cocok dieksekusi tepat satu kali dengan indeks berhenti pada posisi temuan. Isi indeks sebelum SEARCH menentukan titik mulainya, sehingga pola yang lazim adalah SET IDX-MAPEL TO 1 tepat sebelum SEARCH agar seluruh tabel tersapu.

Tabel contoh diisi melalui item FILLER bernilai tetap pada record ISI-TABEL, yang kemudian didefinisikan ulang menjadi tabel melalui REDEFINES. Teknik ini membuat deretan nilai awal tersebut terbaca sebagai entri yang berulang. Setiap entri berukuran 16 byte, terdiri atas kode tiga karakter, nama sepuluh karakter, dan nilai tiga digit.

Satu SEARCH boleh memuat beberapa kondisi WHEN, dan kondisi yang lebih dahulu terpenuhi menentukan hasilnya. Kondisi WHEN juga tidak harus menguji satu kunci tertentu, sehingga pencarian dapat dilakukan atas nama maupun nilai lain yang tersimpan di dalam entri. Kekurangan SEARCH muncul pada tabel besar, karena tabel seribu entri yang tidak memuat nilai yang dicari tetap disapu habis sebelum AT END dinyatakan. Pada skala seperti itu, SEARCH ALL menjadi pilihan yang lebih hemat.

cobol search.cbl 
       IDENTIFICATION DIVISION.
       PROGRAM-ID. SEARCH-UJI.
      *--------------------------------------------------------------
      * SEARCH serial: WHEN untuk yang ditemukan, AT END untuk yang
      * tidak ditemukan. Tabel diisi lewat grup FILLER dan REDEFINES.
      *--------------------------------------------------------------
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 ISI-TABEL.
          05 FILLER PIC X(16) VALUE "MTKMatematika090".
          05 FILLER PIC X(16) VALUE "FISFisika    085".
          05 FILLER PIC X(16) VALUE "KIMKimia     078".
          05 FILLER PIC X(16) VALUE "BIOBiologi   088".
          05 FILLER PIC X(16) VALUE "SEJSejarah   075".
          05 FILLER PIC X(16) VALUE "INDIndonesia 092".
          05 FILLER PIC X(16) VALUE "INGInggris   084".
       01 DAFTAR-MAPEL REDEFINES ISI-TABEL.
          05 ENTRI-MAPEL OCCURS 7 TIMES INDEXED BY IDX-MAPEL.
             10 KODE-MAPEL  PIC X(3).
             10 NAMA-MAPEL  PIC X(10).
             10 NILAI-MAPEL PIC 9(3).
       01 KODE-CARI PIC X(3).
       01 POSISI    PIC 9(2).
       PROCEDURE DIVISION.
       UTAMA.
           MOVE "BIO" TO KODE-CARI
           PERFORM CARI-KODE
           MOVE "JPN" TO KODE-CARI
           PERFORM CARI-KODE
           STOP RUN.
       CARI-KODE.
           SET IDX-MAPEL TO 1
           SEARCH ENTRI-MAPEL
               AT END
                   DISPLAY "Kode " KODE-CARI " tidak ditemukan"
               WHEN KODE-MAPEL (IDX-MAPEL) = KODE-CARI
                   MOVE IDX-MAPEL TO POSISI
                   DISPLAY "Kode " KODE-CARI " ada di posisi " POSISI
                       " dengan nilai " NILAI-MAPEL (IDX-MAPEL)
           END-SEARCH.
text Keluaran 
Kode BIO ada di posisi 04 dengan nilai 088
Kode JPN tidak ditemukan

Pencarian pertama menemukan BIO pada elemen keempat, dan indeks yang berhenti di posisi itu langsung dipakai untuk membaca NILAI-MAPEL (IDX-MAPEL) milik entri yang sama. Pencarian kedua menyapu seluruh tabel tanpa menemukan JPN, sehingga badan AT END yang dieksekusi. Kedua keadaan tersebut wajib ditangani karena keduanya merupakan hasil pencarian yang normal.

Pilihan antara SEARCH dan SEARCH ALL mengikuti sifat tabelnya. SEARCH dipakai bila urutan tabel tidak dapat dijamin atau bila syarat pencariannya beragam, sedangkan SEARCH ALL dipakai bila tabel memang disimpan terurut menurut kuncinya. Tabel yang disusun oleh SORT pada pemrosesan berkas biasanya sudah memenuhi syarat itu, sehingga SEARCH ALL dapat dipakai tanpa persiapan tambahan. Tabel yang tersusun menurun ditangani dengan cara yang sama melalui klausa DESCENDING KEY IS.

Reproduksi keluaran di atas dengan perintah berikut, lalu jalankan ./search.

bash 
# kompilasi program pencarian serial
cobc -x search.cbl

SEARCH ALL untuk pencarian biner#

SEARCH ALL menerapkan pencarian biner, yaitu memeriksa elemen tengah tabel lalu membuang separuh tabel yang mustahil memuat temuan pada setiap langkah. Jumlah perbandingannya tumbuh sekitar O(log⁡n)O(\log n), sehingga tabel tujuh entri cukup diperiksa paling banyak tiga kali. Kecepatan itu hanya diperoleh apabila tabel benar-benar terurut, karena keputusan membuang separuh tabel didasarkan pada urutan tersebut. Syarat deklarasinya adalah klausa ASCENDING KEY IS atau DESCENDING KEY IS pada entri ber-OCCURS yang menyebut item kuncinya, dan kondisi WHEN hanya boleh berupa kesamaan terhadap kunci tersebut. Keadaan tidak ditemukan ditangani AT END seperti pada SEARCH.

cobol search-all.cbl 
       IDENTIFICATION DIVISION.
       PROGRAM-ID. SEARCH-ALL-UJI.
      *--------------------------------------------------------------
      * SEARCH ALL biner: tabel wajib terurut menurut kuncinya.
      *--------------------------------------------------------------
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 ISI-SORT.
          05 FILLER PIC X(16) VALUE "BIOBiologi   088".
          05 FILLER PIC X(16) VALUE "FISFisika    085".
          05 FILLER PIC X(16) VALUE "INGInggris   084".
          05 FILLER PIC X(16) VALUE "INDIndonesia 092".
          05 FILLER PIC X(16) VALUE "KIMKimia     078".
          05 FILLER PIC X(16) VALUE "MTKMatematika090".
          05 FILLER PIC X(16) VALUE "SEJSejarah   075".
       01 DAFTAR-SORT REDEFINES ISI-SORT.
          05 ENTRI-SORT OCCURS 7 TIMES
               ASCENDING KEY IS KODE-SORT
               INDEXED BY IDX-SORT.
             10 KODE-SORT  PIC X(3).
             10 NAMA-SORT  PIC X(10).
             10 NILAI-SORT PIC 9(3).
       01 POSISI PIC 9(2).
       PROCEDURE DIVISION.
       UTAMA.
           SEARCH ALL ENTRI-SORT
               AT END
                   DISPLAY "Kode KIM tidak ditemukan"
               WHEN KODE-SORT (IDX-SORT) = "KIM"
                   MOVE IDX-SORT TO POSISI
                   DISPLAY "Kode KIM ada di posisi " POSISI
                       " dengan nilai " NILAI-SORT (IDX-SORT)
           END-SEARCH
           SEARCH ALL ENTRI-SORT
               AT END
                   DISPLAY "Kode JPN tidak ditemukan"
               WHEN KODE-SORT (IDX-SORT) = "JPN"
                   MOVE IDX-SORT TO POSISI
                   DISPLAY "Kode JPN ada di posisi " POSISI
           END-SEARCH
           STOP RUN.
text Keluaran 
Kode KIM ada di posisi 05 dengan nilai 078
Kode JPN tidak ditemukan

Tabel contoh disusun menaik menurut KODE-SORT, sesuai klausa ASCENDING KEY IS KODE-SORT yang menyertainya. Pencarian KIM menemukan entri pada posisi 05 dan indeks berhenti di sana, sehingga field nilai pada entri yang sama dapat dibaca langsung. Angka 05 merujuk posisi pada tabel terurut ini, dan entri yang sama boleh berada di posisi lain pada tabel yang belum diurutkan. Pencarian JPN gagal karena kunci itu memang tidak ada, dan AT END melaporkannya tanpa perlu menelusuri tabel satu per satu. Tidak ada SET indeks sebelum SEARCH ALL karena verb ini mengelola indeksnya sendiri sejak awal.

Reproduksi keluaran di atas dengan perintah berikut, lalu jalankan ./search-all.

bash 
# kompilasi program pencarian biner
cobc -x search-all.cbl

Kesalahan umum#

  • Lupa mengisi indeks sebelum SEARCH. Pencarian dimulai dari nilai indeks saat itu, sehingga indeks yang tertinggal di akhir tabel dari perulangan sebelumnya membuat pencarian langsung berakhir pada AT END meskipun datanya ada. Tetapkan SET IDX TO 1 sebelum setiap SEARCH.
  • Menjalankan SEARCH ALL pada tabel yang tidak terurut. Hasilnya tidak terdefinisi, yaitu dapat berupa AT END padahal datanya ada, atau posisi yang menunjuk entri yang keliru, karena algoritme membuang separuh tabel berdasarkan asumsi urutan. Urutkan tabel menurut kuncinya lebih dahulu, misalnya dengan SORT.
  • Menulis syarat selain kesamaan pada WHEN milik SEARCH ALL. Bentuk seperti WHEN KODE (IDX) > "ABC" ditolak compiler dengan pesan error: invalid SEARCH ALL condition, karena pencarian biner hanya bekerja dengan kesamaan kunci.

Ringkasan#

  • SEARCH menelusuri tabel secara serial mulai dari nilai indeks saat itu, mengeksekusi WHEN yang cocok atau AT END bila habis, dan wajib dipakai pada tabel dengan INDEXED BY.
  • SEARCH ALL mencari secara biner dengan perbandingan sekitar O(log⁡n)O(\log n) dan mensyaratkan tabel terurut menurut kunci yang dideklarasikan dengan ASCENDING KEY atau DESCENDING KEY serta WHEN berupa kesamaan kunci.
  • Kedua verb meninggalkan register indeks pada posisi temuan, sehingga field lain pada entri yang sama dapat dibaca segera setelah pencariannya berhasil.

Referensi#