Program C untuk carian binari (rekursif dan berulang)

Algoritma carian binari ialah algoritma berdasarkan mekanisme perbandingan dan pembahagian. Algoritma carian binari juga dipanggil carian separuh margin, carian logaritma atau carian binari. Algoritma carian binari untuk mencari kedudukan nilai sasaran dalam tatasusunan yang disusun. Ia membandingkan nilai sasaran dengan elemen tengah tatasusunan. Jika elemen adalah sama dengan elemen sasaran, algoritma mengembalikan indeks elemen yang ditemui. Jika ia tidak sama, algoritma carian menggunakan separuh daripada tatasusunan, bergantung pada perbandingan nilai, algoritma menggunakan separuh pertama (apabila nilai kurang daripada tengah) dan separuh kedua (apabila nilai kurang daripada tengah) dan separuh kedua (apabila nilai lebih besar daripada tengah) . Lakukan perkara yang sama dengan separuh tatasusunan seterusnya.

Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8

Penjelasan

Untuk tatasusunan kami -

kami akan membandingkan 55 dengan elemen tengah tatasusunan 18 yang kurang daripada 55 jadi kami akan menggunakan separuh kedua tatasusunan iaitu tatasusunan {24, 45, 55, 99} , tengah juga 55. Gunakannya untuk menyemak nilai elemen carian. Dan nilai yang dipadankan, maka kita akan mengembalikan indeks nilai sebagai 8.

Jika elemen carian kurang daripada bahagian tengah, maka kita akan menggunakan separuh pertama dan teruskan sehingga elemen ditemui di tengah tatasusunan.

Untuk melaksanakan carian binari, kita boleh menulis kod dalam dua cara. Kedua-dua cara ini hanya berbeza daripada cara kita memanggil fungsi yang menyemak elemen carian binari. Ia adalah:

• Gunakan lelaran - Ini bermakna menggunakan gelung di dalam fungsi untuk menyemak kesamaan unsur perantaraan. < /p>

• Menggunakan Dalam kaedah ini, fungsi memanggil dirinya lagi dan lagi dengan set nilai yang berbeza.

Contoh

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
   int A[] = {0,12,6,12,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,iterativeBsearch(A,10,n));
   return 0;
}
int iterativeBsearch(int A[], int size, int element) {
   int start = 0;
   int end = size-1;
   while(start<=end) {
      int mid = (start+end)/2;
      if( A[mid] == element) {
         return mid;
      } else if( element < A[mid] ) {
         end = mid-1;
      } else {
         start = mid+1;
      }
   }
   return -1;
}

Output

55 is found at Index 8

Contoh

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
   if(start>end) return -1;
      int mid = (start+end)/2;
   if( A[mid] == element ) return mid;
   else if( element < A[mid] )
      RecursiveBsearch(A, start, mid-1, element);
   else
      RecursiveBsearch(A, mid+1, end, element);
}
int main() {
   int A[] = {0,2,6,11,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,RecursiveBsearch(A,0,9,n));
   return 0;
}

Output

55 is found at Index 8

Atas ialah kandungan terperinci Program C untuk carian binari (rekursif dan berulang). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!