Information Technology VietNam

Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

    Tìm kiếm nhị phân - Binary search

    Vy Thanh Định
    Vy Thanh Định
    Web Master
    Web Master


    Giới tính : Nam Bài gửi : 228
    Tổng Điểm : 544
    Điểm Thưởng : 16
    Sinh Nhật : 19/05/1990 Bị Dụ Dỗ : 11/09/2009
    Tuổi : 34

    Tìm kiếm nhị phân - Binary search Empty Tìm kiếm nhị phân - Binary search

    Bài gửi by Vy Thanh Định 28/11/2009, 18:13

    Code:


    #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');
    }

      Hôm nay: 25/11/2024, 15:37