/*
có 3 loại thuật toán tìm kiếm
+
Tìm kiếm tuần tự vét cạn
+
Tìm kiến lính canh
+
Tìm kiếm nhị phân
*/
#include<iostream>
using namespace std;
int timkiemtuantuvetcan(double a[],int n,int x)
{
for (int i = 0; i < n; i++)
{
if (a[i] == x)
{
return i;
}
}
return -1;
}
/*
Ý tưởng thuật toán tìm kiếm linh canh
đưa phần tử cần tìm vào cuối mãng sau đó duyệt xem trong mãg có tồn tại phần tử nào cần tìm không nếu trùng thì return lại vị trí đó
con nếu nó trúng với vị trí cuối cùng của mảng thì retun -1 khong tìm thấy
*/
int timkiemtuantulinhcanh(double a[], int n, int x)
{
a[n] = x;
for (int i = 0;; i++)
{
if (a[i] == x)
{
return i;
}
}
}
// tìm kiếm nhị phân
// bản chất của thuật toán tìm kiếm nhị phân là
/*
ý tưởng thuật toán
// diều kiện thuật toán này là
dãy phải được xắp xếp tăng hoặc giảm dần
ban đầu cho
left=0;
right=n-1;
điều kiện hợp lệ là left phải nhỏ hơn right while(left<=right)
có 1 biến trung gian mid
mid=(left+right)/2;
diều kiện :
mid==x thì trả về x;
nếu không
if(x>a[mid](lớn hơn phần tử trung tâm))--> dịch phần tử trung tâm mid sang bên phải và gán nó thành left (left=mid(phần tử trung tâm)+1)
else(x<a[mid](nhỏ hơn phần tử trung tâm ))--> dịch phần tử trung tâm mid sang bên trái và gán nó thành right (right=mid(phần tử trung tâm)-1)
vd: a[] 1 2 3 4 5 6 7 8 9 10
phần tử cần tìm 6;
Ban đầu:
left=0;
right=9;
--> 0<9
mid=(9+0)/2=4.5-->4
6(x)>5(a[4])
left-->mid+1-->4+1=5;
left=5;
right=9;
-->5<9;
mid=(5+9)/2=7;
6(x)<(a[7])8
right=7-1=6;
left=5;
right=6;
5<6
mid=(5+6)/2=5.5==>5
a[5]=6==return mid =5;
*/
int timkiemnhiphan(double a[],int n,int x)
{
int left = 0;
int 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;
}
}
return -1;
}
/// dùng hàm đệ quy cài đặt thuật toán tìm kiếm nhị phân
int dequytimkiemnhiphan(double a[], int n, int x,int mid=0)
{
int left = 0;
int right = n - 1;
mid = (left + right) / 2;
if (left>right)
{
return -1;
}
(x > a[mid])?left = mid + 1: right = mid - 1;;
return dequytimkiemnhiphan(a, n, x, mid);
}
int main()
{
double a[] = { 1,2,3,4,5,6,7,8,9,10};
int n = 7;
int x = 12;
int k = timkiemnhiphan(a, n, x);
if (k == -1)
{
cout << "\nKhong ton tai phan tu can tim xin kiem tra lai!";
}
else
{
cout << "\nphan tu can tim nam o vi tri thu: " << k;
}
system("pause");
return 0;
}
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.