查找

顺序查找和二分查找

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

typedef struct SS{
    int* elem;
    int TableLen;
}SSTable;
//初始化
void ST_Init(SSTable& ST, int len)
{
    ST.TableLen = len + 1;//多申请了一个位置,为了存哨兵
    ST.elem = (int*)malloc(sizeof(int) * ST.TableLen);
    int i;
    srand(time(NULL));//随机数生成
    for (i = 0; i < ST.TableLen; i++)//为啥这里零号位置也随机了数据，为折半查找服务
    {
        ST.elem[i] = rand() % 100;
    }
}
//打印
void ST_print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; i++)
    {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}
//顺序查找
int Search_Seq(SSTable ST, int key) {
    //哨兵
    ST.elem[0] = key;
    int i;
    for (i=ST.TableLen -1; ST.elem[i] != key; --i);

    return i;
}
//二分查找
int Binary_Search(SSTable ST, int key) {
    int low = 0, high = ST.TableLen - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (ST.elem[mid] == key) {
            return mid;
        }
        else if (ST.elem[mid] < key) {
            low = mid + 1;
        }
        else if (ST.elem[mid] > key) {
            high = mid - 1;
        }
    }
    return -1;
}
int compare(const void* left, const void* right)
{
    return *(int*)left - *(int*)right;
}
int main() {
    SSTable ST;
    int key;
    int pos;//存储查询元素的位置
    ST_Init(ST, 10);
    ST_print(ST);
    printf("请输入要搜索的key值:\n");
    scanf("%d", &key);
    pos = Search_Seq(ST, key);
    if (pos)
    {
        printf("查找成功 位置为 %d\n", pos);
    }
    else {
        printf("查找失败\n");
    }

    qsort(ST.elem, ST.TableLen, sizeof(int), compare);//qsort实现的是快排

    ST_print(ST);
    printf("二分查找，请输入要搜索的key值:\n");
    scanf("%d", &key);
    //有序数组
    pos = Binary_Search(ST, key);
    if (pos != -1)
    {
        printf("查找成功 位置为 %d\n", pos);
    }
    else {
        printf("查找失败\n");
    }
    return 0;
}