binary search.cpp

Binary search Ham binsearch la mot ham de qui, giup tim gia tri tren mang so a[].Neu ham tra ve tri

/*****************************************************************************
* Chuong trinh C1-3: tim kiem nhi phan - binary search                       *
* Nguoi viet chuong trinh: Nguyen Hong Chuong                                *
* Ngay cap nhat moi nhat: 15/3/1999                                          *
*****************************************************************************/

#include <stdio.h>
#include <conio.h>

/* Ham binsearch la mot ham de qui, giup tim giatri tren mang so a[].
   Neu ham tra ve tri -1 la khong tim thay, neu ham tra ve tri khac -1
   la tim thay tai vi tri la gia tri tra ve */
int binsearch(int a[], int dau, int cuoi, int giatri)
{
   int giua;
   giua = (dau+cuoi)/2;

   // Dieu kien dung
   if(dau > cuoi)            // khong tim thay
      return(-1);
   if(giatri == a[giua])     // tim thay tai vi tri giua
      return(giua);

   // Buoc de qui
   if(giatri < a[giua])
      return(binsearch(a, dau, giua-1, giatri));
   else
      return(binsearch(a, giua+1, cuoi, giatri));
}

void main()
{
   int i, a[10], giatri;
   char c;

   clrscr();
   printf("\n***Tim kiem nhi phan***\n");
   printf("\nHay nhap 10 so nguyen tu nho den lon: \n");
   for(i = 0; i < 10 ; i++)
      scanf("%d", &a[i]);

   // in ra man hinh de kiem tra
   printf("\nCac so ban da nhap la: \n");
   for(i = 0; i < 10 ; i++)
      printf("[%d]:%d  ", i+1, a[i]);

   do
   {
      printf("\n\nNhap so can tim: ");
      scanf("%d", &giatri);
      i = binsearch(a, 0, 9, giatri);  // i la vi tri tim thay
      if(i == -1)
	      printf("Khong tim thay");
      else
	      printf("Tim thay tai vi tri %d", i);
      printf("\n\nTim nua khong? (c/k): ");
      c = getche();
   } while(c == 'c' || c == 'C');
}