Page 238 - MODUL ALGORTIMA DAN PEMROGRAMAN

• Fungsi ini menerima 3 parameter:
o array: Array yang akan dicari datanya (tipe int).
o n: Jumlah elemen dalam array (tipe int).
o dataDicari: Nilai yang ingin dicari dalam array (tipe int).
• Fungsi ini mengembalikan nilai int:
o Indeks elemen array yang berisi nilai dataDicari jika ditemukan.
o Nilai -1 jika data tidak ditemukan.
• Algoritma pencarian menggunakan loop while dengan kondisi low <= high.
o low dan high mewakili indeks awal dan akhir dari bagian array yang sedang dicari.
• Pada setiap iterasi loop:
o Hitung mid menggunakan rumus interpolasi yang melibatkan nilai dataDicari,
array[low], dan array[high].
o Bandingkan array[mid] dengan dataDicari:
▪ Jika sama, kembalikan mid sebagai indeks yang ditemukan.
▪ Jika array[mid] < dataDicari, perbarui low menjadi mid + 1 untuk mencari di bagian
kanan array.
▪ Jika array[mid] > dataDicari, perbarui high menjadi mid - 1 untuk mencari di bagian
kiri array.
• Jika loop selesai dan low > high, artinya data tidak ditemukan, kembalikan -1.
2) Fungsi main:
• Sama seperti pada program binary search sebelumnya, fungsi ini mendeklarasikan
variabel, meminta input dari pengguna, dan menampilkan hasil pencarian.
• Perbedaan utama terletak pada pemanggilan fungsi pencarian:
o Dalam program ini, fungsi interpolationSearch digunakan untuk mencari data dengan
parameter array, jumlah elemen, dan nilai yang dicari.

5. Program

#include <iostream>

using namespace std;

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

while (low <= high) {
int mid = (low + high) / 2;

if (arr[mid] == target) {
return mid; // Angka ditemukan, kembalikan indeks
} else if (arr[mid] < target) {
low = mid + 1; // Perbarui low untuk mencari di bagian kanan
} else {
high = mid - 1; // Perbarui high untuk mencari di bagian kiri
}
}

return -1; // Angka tidak ditemukan, kembalikan -1
}

int main() {
// Daftar angka yang sudah diurutkan
229
int arr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, 97};
int n = sizeof(arr) / sizeof(arr[0]); // Hitung jumlah elemen array

// Kasus 1: Cari angka 67
int target = 67;