1.順序搜尋
2.基于順序表的折半搜尋
3.二叉搜尋樹
#include<iostream>
using namespace std;
int Seqsearch(int r[], int n, int k) {//順序搜尋(帶哨兵)
r[0] = k;
while (r[n--] != k) {};
return n+1;
}
int Binsearch1(int r[], int n, int k) {//順序表的折半搜尋(非遞歸)
int low = 1, high = n;
while (low <= high) {
int middle = (low + high) / 2;
if (r[middle] < k)low = middle + 1;
else if (r[middle] > k)high = middle - 1;
else return middle;
}return 0;
}
int Binsearch2(int r[], int low, int high, int k) {//順序表的這般搜尋(遞歸)
if (low > high)return 0;
int middle = (low + high) / 2;
if (r[middle] < k)Binsearch2(r, middle + 1, high, k);
else if (r[middle] > k)Binsearch2(r, low, middle - 1,k);
else return middle;
}
int main() {
int a[101],n,x;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++)scanf_s("%d", &a[i]);
scanf_s("%d", &x);
//cout<<Seqsearch(a, n, x);
//cout<<Binsearch1(a, n, x);
cout << Binsearch2(a, 1, n, x);
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
int tree[1001] = { 0 };
int sum = 0, n, x, a[1001];
void insert(int x)
{
int t = 1;//從根節點開始
while (tree[t] != 0){
if (tree[t] > x) t *= 2;
else t = t * 2 + 1;
}
tree[t] = x;
}
int find_x(int y)
{
int t = 1;
if (*find(a, a + n, y)) {
while (tree[t] != y || tree[t] == 0){
sum++;
if (tree[t] > y) t *= 2;
else t = t * 2 + 1;
}
if (!tree[t]) return -1;
else return sum + 1;
}
else return -1;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
insert(a[i]);
}
cin >> x;
int ans = find_x(x);
if (ans != -1) cout << ans;
else cout << "NO";
}