Tìm kiếm nhị phân (Binary Search) trong C

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly the data collection should be in sorted form.

Chương trình minh họa Tìm kiếm nhị phân (Binary Search) trong C

#include <stdio.h>

#define MAX 20

// khai bao mang 
int intArray[MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,55,66};

void printline(int count){
   int i;
	
   for(i = 0;i <count-1;i++){
      printf("=");
   }
	
   printf("=\n");
}

int find(int data){
   int lowerBound = 0; // chi muc ban dau
   int upperBound = MAX -1; // chi muc cuoi
   int midPoint = -1;
   int comparisons = 0;      
   int index = -1;
	
   while(lowerBound <= upperBound){
      printf("So sanh lan thu %d\n" , (comparisons +1) ) ;
      printf("Chi muc ban dau : %d, intArray[%d] = %d\n", 
		lowerBound,lowerBound,intArray[lowerBound]);
      printf("Chi muc cuoi : %d, intArray[%d] = %d\n", upperBound,upperBound,intArray[upperBound]);
      comparisons++;
		
      // uoc luong gia tri tai vi tri trung vi 
      // midPoint = (lowerBound + upperBound) / 2;
      midPoint = lowerBound + (upperBound - lowerBound) / 2;	
		
      // tim thay du lieu
      if(intArray[midPoint] == data){
         index = midPoint;
         break;
      }else {
         // neu du lieu la lon hon 
         if(intArray[midPoint] < data){
            // tim kiem du lieu phan lon hon
            lowerBound = midPoint + 1;
         }
         // neu du lieu la nho hon 
         else{           
            // tim kiem du lieu phan nho hon
            upperBound = midPoint -1;
         }
      }               
   }
   printf("So phep tinh so sanh thuc hien: %d" , comparisons);
   return index;
}

void display(){
   int i;
   printf("[");
	
   // duyet qua tat ca phan tu 
   for(i = 0;i<MAX;i++){
      printf("%d ",intArray[i]);
   }
	
   printf("]\n");
}

main(){
   printf("Mang du lieu nhap vao: ");
   display();
   printline(50);
	
   //Tim vi tri cua 55
   int location = find(55);

   // neu phan tu duoc tim thay 
   if(location != -1)
      printf("\nTim thay phan tu tai vi tri: %d" ,(location+1));
   else
      printf("\nKhong tim thay phan tu.");
}

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.