Pencarian

Pencarian adalah proses menemukan posisi elemen tertentu dalam urutan elemen. 

Algoritma pencarian adalah algoritma yang diberi argumen x dan mencoba menemukan elemen dengan nilai x dalam himpunan nilai tertentu. Jadi, pencarian elemen dengan nilai tersebut mungkin tidak berhasil jika elemen itu tidak ada. 

Ada sejumlah teknik dan metode pencarian, tetapi di C++ kamu akan mempelajari:

• Pencarian Linear
• Pencarian Biner

Pencarian Linear

Pencarian Linear adalah teknik pencarian paling dasar dan juga mudah diterapkan di C++. Dalam pencarian linear, sesuai namanya, kunci yang dicari dibandingkan secara berurutan dengan setiap elemen dalam urutan data sampai ditemukan atau urutannya berakhir.

Linear Search(sequence, key)
	for each item in sequence:
		if item == key
			return item's index

Dalam kode nyata, pencarian linear akan terlihat seperti ini:

int linear_search(int array[], int n, int x)
{
	for(int i = 0; i < n; i++)
		if(array[i] == x)
			return i;
	return 0;
}

int main()
{
	int array[] = {1, 2, 3, 4, 5};
	int n = 5;
	int x = 3;
	
	cout << "The index of the element " << x << " is " << linear_search(array, n, x);

Output:
The index of the element 3 is 2

Seperti yang bisa kamu lihat dari kode di atas, fungsi pencarian linear pada dasarnya melakukan perulangan pada urutan elemen sampai menemukan kecocokan. Jika tidak menemukan kecocokan, fungsi ini mengembalikan -1.

Pencarian Biner

Pencarian Biner adalah algoritma pencarian untuk menemukan posisi elemen, tetapi array harus sudah diurutkan.
Algoritma pencarian biner menggunakan teknik "bagi dan taklukkan" untuk mencari kunci. Urutan elemen berulang kali dibagi menjadi dua, lalu elemen dicari di bagian yang lebih mendekati.

Misalkan kita sedang mencari elemen x = 4

Jadi, kode untuk pencarian biner akan terlihat seperti ini.

int binarySearch(int array[], int x, int left, int right) {
  
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      left = mid + 1;

    else
      right  = mid - 1;
  }

  return -1;
}

int main()
{
    int array[] = {1, 5, 8, 10, 20};
    int x = 10;
    int n = 5;
    int result = binarySearch(array, x, 0, n - 1);
    
    if(result == -1)
    	cout << "Not found.";
    else
    	cout << "The element is found at " << result;

Output:
The element is found at 3

Ingat apa itu pencarian, apa tujuannya, dan untuk apa kita menggunakannya. Ingat juga cara menerapkan pencarian linear dan pencarian biner. Terus latih teknik tingkat lanjut di C++ melalui latihan.