【数据结构】顺序查找和二分查找

顺序查找，elem[0]作为哨兵位置，避免判断数组越界等敏感操作，Search_Seq返回元素在顺序表中的位置

#include<iostream>
using namespace std;
const int MAX = 0xffff;
typedef struct Table {
    int elem[MAX];
    int length;
}Table;

int Search_Seq(Table tb, int key) {
    tb.elem[0] = key;
    int i = 0;
    for (i = tb.length; tb.elem[i] != key; --i);
        return i;
}

void InitTable(Table &tb) {
    tb.length = 100;
    for (int i = 1; i <= tb.length; i++)
        tb.elem[i] = i*i;
}
int main() {
    Table tb;
    InitTable(tb);
    cout<<Search_Seq(tb, 81);
    return 0;
}

二分查找，包括迭代版和递归版，函数返回元素在有序表中的位置

#include<iostream>
#include<ctime>
#include<algorithm>
using namespace std;
const int MAX = 0xffff;
int elem[MAX];
bool flag[MAX] = {false};

void InitElem() {
    srand((int)time(0));
    for (int i = 0; i < MAX; i++)
        elem[i] = rand()%10000;
    sort(elem, elem + MAX);
}

// 非递归版
int Binary_Search1(int key) {
    int low = 0, high = MAX - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (elem[mid] == key)
            return mid;
        else if (elem[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

// 递归版
int Binary_Search2(int key, int low, int high) {
    int mid = (low + high) / 2;
    if (elem[mid] == key)
        return mid;
    else if (elem[mid] > key)
        return Binary_Search2(key, low, mid - 1);
    else
        return Binary_Search2(key, mid + 1, high);
    return -1;
}

int main()
{
    InitElem();
    cout<<Binary_Search1(5000)<<endl;
    cout<<Binary_Search2(5000, 0, MAX - 1)<<endl;
    return 0;
}