Pelaksanaan carian binari (rekursif dan berulang) dalam program C

Carian binari ialah algoritma carian yang digunakan untuk mencari kedudukan elemen (nilai sasaran) dalam tatasusunan yang disusun. Tatasusunan harus diisih sebelum menggunakan carian binari.

Carian binari juga dipanggil carian logaritma, carian binari dan carian separa selang.

Cara ia berfungsi

Algoritma carian binari berfungsi dengan membandingkan elemen yang akan dicari dengan elemen tengah tatasusunan dan melakukan proses yang diperlukan berdasarkan hasil perbandingan ini.

Kes 1 - elemen = nilai tengah, cari elemen dan kembalikan indeks.

Kes 2 - elemen > nilai tengah, cari elemen dalam subarray diindeks dari +1 tengah hingga n.

Kes 3 - elemen

Algoritma

Parameter nilai awal, nilai akhir

Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

Fungsi pelaksanaan algoritma carian binari menggunakan fungsi panggilan berulang. Panggilan ini boleh terdiri daripada dua jenis:

• berulang
• rekursif

panggilan berulang sedang menggelungkan sekeping kod yang sama beberapa kali.

Panggilan rekursif ialah memanggil fungsi yang sama berulang kali.

Atur cara untuk melaksanakan carian binari menggunakan panggilan berulang

Contoh

Demonstrasi

#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
   while (start_index <= end_index){
      int middle = start_index + (end_index- start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] < element)
         start_index = middle + 1;
      else
         end_index = middle - 1;
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 16;
   int found_index = iterativeBinarySearch(array, 0, n-1, element);
   if(found_index == -1 ) {
      printf("Element not found in the array ");
   }
   else {
      printf("Element found at index : %d",found_index);
   }
   return 0;
}

Output

Element found at index : 4

Atur cara untuk melaksanakan carian binari menggunakan panggilan rekursif

Contoh

Contoh dalam talian

rreeee

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