#include<stdio.h>
#include<conio.h>
#define MAX 100
void NhapMang(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("\nNhap vao phan tu a[%d] = ", i);
scanf_s("%d", &a[i]);
}
}
void XuatMang(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%4d", a[i]);
}
}
// Tìm kiếm tuần tự vét cạn
// Tìm thấy x trả về vị trí, còn không trả về -1
int TimKiemTuanTuVetCan(int a[], int n, int x)
{
for (int i = 0; i < n; i++)
{
if (a[i] == x)
{
return i;
}
}
return -1;
}
// Tìm kiếm tuần tự lính canh: Bỏ việc xét i < n đi do chắc chắn sẽ tìm thấy ( vì x đã được thêm vào đứng cuối )
int TimKiemTuanTuLinhCanh(int a[], int n, int x)
{
a[n] = x; // Đưa x vào đứng cuối cùng
for (int i = 0; ; i++)
{
if (a[i] == x)
{
return i;
}
}
}
int TimKiemNhiPhan(int a[], int n, int x)
{
int Left = 0, Right = n - 1;
while (Left <= Right)
{
int Mid = (Left + Right) / 2;
if (x > a[Mid])
{
Left = Mid + 1;
}
else if (x < a[Mid])
{
Right = Mid - 1;
}
else
{
return Mid; // tìm thấy
}
}
return -1; // Không tìm thây
}
int main()
{
int n;
do
{
printf("\nNhap vao so luong phan tu cua mang: ");
scanf_s("%d", &n);
if (n < 0 || n > MAX)
{
printf("\nSo luong phan tu khong hop le. Xin kiem tra lai !");
}
} while (n < 0 || n > MAX);
int a[MAX];
NhapMang(a, n);
XuatMang(a, n);
int x;
printf("\nNhap vao phan tu x can tim kiem: ");
scanf_s("%d", &x);
/*int ViTri = TimKiemTuanTuVetCan(a, n, x);
if (ViTri == -1)
{
printf("\nKhong tim thay");
}
else
{
printf("\nPhan tu x nam tai vi tri %d ", ViTri);
}*/
/*int ViTri1 = TimKiemTuanTuLinhCanh(a, n, x);
if (ViTri1 == n)
{
printf("\nKhong tim thay");
}
else
{
printf("\nPhan tu x nam tai vi tri %d ", ViTri1);
}*/
int ViTri2 = TimKiemNhiPhan(a, n, x);
if (ViTri2 == -1)
{
printf("\nKhong tim thay");
}
else
{
printf("\nPhan tu x nam tai vi tri %d ", ViTri2);
}
_getch();
return 0;
}