thuật toán tìm kiếm tuyến tính cải tiến trên dãy đã sắp xếp

thuật toán tìm kiếm tuyến tính cải tiến trên dãy đã sắp xếp
#include<iostream>
using namespace std;
int tim(int *a,int n,int x)
{
int i=0;
while(a[i]!=x && i<n) i++;
if(i==n) return 0;
return i;
}
int tim1(int *a,int n,int x)
{
int i=0;
a[n]=x;
while(a[i]!=x) i++;
if(i==n) return 0;
return i;

}
int tim2caitien(int *a,int n,int x)
{
int i=0;
a[n]=x;
while(a[i]<x) i++;
if(i<n && a[i]==x) return i;
return 0;
}
void main()
{
int a[11]={1,3,6,7,10,11,13,24,45,46},x;
cout<<"tim so x=";
cin>>x;
if(int t=tim2caitien(a,10,x)) cout<<"tim thay tai vi tri: "<<t<<"\n";
else cout<<"khong tim thay";

}

thuật toán tìm kiếm nhị phân bằng đệ quy

//thuật toán tìm kiếm nhị phân bằng đệ quy
#include<iostream>
using namespace std;
int tim(int *a,int left,int right,int x)
{
int m;
if(left>right) return 0;
m=(left+right)/2;
if(a[m]==x) return m;
if(x<a[m]) return tim(a,left,m-1,x);
return tim(a,m+1,right,x);
}
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int x;
cout<<"tim so: ";cin>>x;
if(int z=tim(a,0,9,x)) cout<<"tim thay tai vi tri: "<<z<<"\n";
else cout<<"khong tim thay\n";

}

thuật toán tìm kiếm nhị phân

/*thuật toán tìm kiếm nhị phân
Được áp dụng trên mảng đã có thứ tự.
Ý tưởng: .
Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có
ai-1<ai<ai+1
Nếu X>ai thì X chỉ có thể xuất hiện trong đoạn [ai+1, an-1]
Nếu X<ai thì X chỉ có thể xuất hiện trong đoạn [a0,   ai-1]
Ý tưởng của giải thuật là tại mỗi bước ta so sánh X với phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nữa dưới hay nữa trên của dãy tìm kiếm hiện hành.
Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright, các bước của giải thuật như sau:
Bước 1: left=0; right=N-1;
Bước 2:
mid=(left+right)/2; //chỉ số phần tử giữa dãy hiện hành
So sánh a[mid] với x. Có 3 khả năng
a[mid]= x: tìm thấy. Dừng
a[mid]>x :  Right= mid-1;
a[mid]<x : Left= mid+1;
Bước 3: Nếu Left <=Right ; //  còn phần tử trong dãy hiện  hành
+ Lặp lại bước 2
Ngược lại : Dừng
Hàm trả về giá trị 1 nếu tìm thấy, ngược lại hàm trả về giá trị 0

*/
#include<iostream>
using namespace std;
int tim(int a[], int left,int right, int x)
{
do
{
if (x == a[(left + right) / 2]) return 1;
if (a[(left + right) / 2] > x) right = (left + right) / 2 - 1;
else left = (left + right) / 2 + 1;
} while (left <= right);
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << tim(a, 0, 9, 1);
}

thuật toán tìm kiếm tuyến tính

/*thuật toán tìm kiếm tuyến tính
Cho danh sách có n phần tử a0, a1, a2…, an-1.
Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính.
Tìm phần tử có khoá bằng X trong mảng
Giải thuật tìm kiếm tuyến tính (tìm tuần tự)
Giải thuật tìm kiếm nhị phân
Lưu ý: Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C.
Ý tưởng : So sánh X lần lượt với phần tử thứ 1, thứ 2,…của mảng a cho đến khi gặp được khóa cần tìm, hoặc tìm hết mảng mà không thấy.
Các bước tiến hành
Bước 1: Khởi gán i=0;
Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả năng
+ a[i] == x tìm thấy x. Dừng;
+ a[i] != x sang bước 3;
Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng
Nếu i==N: Hết mảng. Dừng;
Ngược lại: Lặp lại bước 2;
Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0:
int LinearSearch(int a[],int n, int x)
{
int i=0;
while((i<n)&&(a[i]!=x))
i++;
if(i==n)
return 0; //Tìm không thấy x
else
return 1; //Tìm thấy
}Nhận xét: Số phép so sánh của thuật toán trong trường hợp xấu nhất là 2*n.
Để giảm thiểu số phép so sánh trong vòng lặp cho thuật toán, ta thêm phần tử “lính canh” vào cuối dãy.
int LinearSearch(int a[],int n, int x)
{ int i=0; a[n]=x;   // a[n] là phần tử “lính canh”
while(a[i]!=x) 
i++;
if(i==n)
return 0; // Tìm không thấy x
else
return 1; // Tìm thấy
}

*/
#include<iostream>
using namespace std;
int tim(int a[], int n,int x)
{
for (int i = 0; i < n;i++) if (x == a[i]) return i+1;
return 0;
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int x;
cout << "nhap gia tri muon tim: ";
cin >> x;
int vt = tim(a, 10, x);
if (vt !=0) cout << "tim thay tai vi tri: " << vt << "\n";
else cout << "khong tim thay\n";
}