Thuật toán tìm kiếm nhị phân trên mảng, lỗi không tìm kiếm được?

[magician1611]

Bài này là nhập một mảng một chiều , tìm kiếm phần tử x theo nhị phân . Em viết code , phần sắp xếp tăng thì ok , còn phần tìm kiếm ko biết lỗi gì . mấy bro giúp giùm em nhé

C Code:

Lựa chọn code | Ẩn/Hiện code

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

void Nhap_mang(int a[] , int &n)
{
    printf(" Nhap so phan tu mang : ");
    scanf("%d" , &n);
    for(int i = 0 ; i<n ; i++)
    {
        printf("a[%d] = " , i);
        scanf("%d" , &a[i]);
    }
}

void Xuat_mang(int a[] , int n)
{
    for(int i = 0 ; i<n ; i++)
    printf("%d   " , a[i]);
}

void Swap (int &a,int &b)
{
    int t = a;
    a=b;
    b=t;
}


void Sap_xep_tang (int a[] , int n)
{
    int i,j;
    for(i = 0;i<n-1 ; i++)
       for(j = n-1 ; j>i ; j--)
          if(a[j] < a[j-1])
         Swap(a[j] , a[j-1]);
}

int Tim_nhi_phan (int a[] , int n , int x)
{
    int l = 0 , r = n - 1 , k;
    while (l<=r)
    {
        k = (l+r)/2;
        if(a[k] == x)
        return k;
        if(a[k]<x)
        k = l+1;
        else
        k = r-1;
    }
    return -1;
}

void main()
{
    clrscr();
    int a[20],n,x;
    Nhap_mang (a,n);
    printf(" Mang vua nhap : ");
    Xuat_mang (a,n);
    printf("\nMang duoc sap xep tang: ");
    Sap_xep_tang (a,n);
        Xuat_mang(a,n);
    printf("\n Nhap phan tu x can tim : ");
    scanf("%d" , &x);
    int c = Tim_nhi_phan (a,n,x);
    if (c == -1)
    printf("Ko tim thay phan tu %d", x);
    else
        printf("Tim duoc phan tu %d tai vi tri %d" , x , c);
    getch();
}

[AlexF]

C Code:

Lựa chọn code | Ẩn/Hiện code

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

void Nhap_mang(int a[] , int &n)
{
    printf(" Nhap so phan tu mang : ");
    scanf("%d" , &n);
    for(int i = 0 ; i<n ; i++)
    {
        printf("a[%d] = " , i);
        scanf("%d" , &a[i]);
    }
}

void Xuat_mang(int a[] , int n)
{
    for(int i = 0 ; i<n ; i++)
    printf("%d   " , a[i]);
}

void Swap (int &a,int &b)
{
    int t = a;
    a=b;
    b=t;
}


void Sap_xep_tang (int a[] , int n)
{
    int i,j;
    for(i = 0;i<n-1 ; i++)
       for(j = n-1 ; j>i ; j--)
          if(a[j] < a[j-1])
         Swap(a[j] , a[j-1]);
}

int Tim_nhi_phan (int a[] , int n , int x)
{
    int l = 0 , r = n - 1 , k;
    while (l<=r)
    {
        k = (l+r)/2;
        if(a[k] == x)
            return k;
        else if(a[k]<x)
            r = k-1;
        else
            l = k+1;
    }
    return -1;
}

void main()
{
    int a[20],n,x;
    Nhap_mang (a,n);
    printf(" Mang vua nhap : ");
    Xuat_mang (a,n);
    printf("\nMang duoc sap xep tang: ");
    Sap_xep_tang (a,n);
        Xuat_mang(a,n);
    printf("\n Nhap phan tu x can tim : ");
    scanf("%d" , &x);
    int c = Tim_nhi_phan (a,n,x);
    if (c == -1)
    printf("Ko tim thay phan tu %d", x);
    else
        printf("Tim duoc phan tu %d tai vi tri %d" , x , c);
    getch();
}

bài của bạn triển khai thuật toán bị nhầm ,mình sửa lại rồi

[QuangHoang]

Tạm sửa như này, bạn test thử xem
Chú ý là trước khi tìm kiếm phải sắp xếp đã.

C Code:

Lựa chọn code | Ẩn/Hiện code

int Tim_nhi_phan (int a[] , int n , int x)
{
    int l = 0 , r = n - 1 , k;
    while (l<=r)
    {
        k = (l+r)/2;
        if(a[k] == x)
             return k;
        if(x<a[k])
                 r = k-1;
        else
             l = k+1;
    }
    return -1;
}

@Edit: Chậm hơn coder_gate 1 bước

[magician1611]

bài sửa của coder_gate sai oi
vẫn ko tìm được x
bạn hoàng code chính xác
thanks các bro nhiều

[htran6751]

giúp giùm mình với.mình cũng vik code giải thuật tìm kiếm nhị phân nhưng bị lỗi.chạy ra kết quả không đúng.

C Code:

Lựa chọn code | Ẩn/Hiện code

#include<iostream.h>
void nhapmang(int a[], int &n)
{
  cout<<"Nhap vao so n: ";cin>>n;
  for (int i=0;i<n;i++)
  {
    cout<<"a["<<i<<"]: ";
    cin>>a[i];
  }
}

void xuatmang(int a[], int n)
{
     cout<<endl;
     for (int i=0;i<n;i++)
      cout<<a[i]<<" ";
}
int tknp(int a[],int s)
{
    int n;
    int i,start=0,end=n,found=0;
    do
    {
        i=(end+start)/2;
        if(a[i]==s)
        found=1;
        else if (a[i]<s)
        start=i+1;
        else if (a[i]>s)
        end=i-1;
    }
    while(!found&&end>=start);
    if(found==1)
    return i+1;
    else
    return 0;
}
void main()
{
    int a;
    int b;
    int x[100];
    int n;
    int s;
    nhapmang(x,n);
    cout<<"mang vua nhap:\n";
    xuatmang(x,n);
    cout<<"nhap vao so can tim";
    cin>>s;
    b=tknp(x,s);
    if(b==0)
    cout<<"khong co";
    else
    cout<<"vi tri "<<b;
   
}

[nangtienxanhhanhphuc]

Bạn xem lại thuật toán tìm kiếm của Quanghoang và các phần còn lại của magician1611 nha.Bài của bạn còn thiếu phần sắp xếp.Ak mình không hiểu 1 vấn đề nữa là tại sao khi khai bao tham số cho phần Nhapmang có int &n ???(Bạn nên code đẹp hơn để mọi người dễ nhìn và dễ sửa bài cho bạn)

[clchicken]

Có int &n để bạn ấy muốn nhập n ở trong hàm.
Khi ra khỏi hàm thì n mang giá trị đã bị thay đổi lần cuối cùng ở trong hàm.

[coolkg1412]

mình có cái code tìm kiếm nhị phân nè (binary search) bạn thữ xem sao :

C++ Code:

Lựa chọn code | Ẩn/Hiện code

giả sữ ta có mảng A có n phần tử, tăng dần cần tìm x trong A

int biSearch (int *_a,int x,int n)
{
    int i = 0;
   
   while (i < n)
   {
       int mid = (i + n) / 2 // Lấy phần tử ở giữa;

       if(_a[mid] <x) n = mid; // nếu x > a[mid] thì tìm trong nữa đầu
       else
            if(_a[mid] > x) i=mid + 1;   // ngược lại tìm trong nữa sau
            else
                 if (_a[mid] == x) return mid; // nếu a[mid]== x trả về vị trí tìm thấy
   }
   
   return -1;  // không tìm thấy trả về -1
}

[orchidshl1]

rất bổ ích, thanks các bro