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ả:

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.