顺序查找,折半查找

顺序查找：

#include<iostream>
#include<cstdio>
#include<malloc.h>

typedef struct{
    int *elem;
    int length;
}SSTable;

void Init_SSTable(SSTable &L){
    L.length=10;
    L.elem=(int *)malloc(L.length*sizeof(int));
    for(int i=1;i<=9;i++){
        scanf("%d",&L.elem[i]);
    }
}

int Search_Seq(SSTable L,int key){
    L.elem[0]=key;//设置哨兵
    for(int i=L.length-1;i>=0;i--){
        if(L.elem[i]==key){
            return i;//都有返回值，返回值为0时，表示查找失败
        }
    }
}

int main(){
    SSTable T;
    Init_SSTable(T);
    printf("输入关键字\n");
    int key;
    scanf("%d",&key);
    printf("位置为（0表示查找失败）：%d\n",Search_Seq(T,key));
}

总结：

1.顺序查找使用于关键字无序的情形

2.ASL=(1+n)/2

折半查找：

#include<iostream>
#include<cstdio>
#include<malloc.h>


typedef struct{
    int *elem;
    int length;
}SSTable;


void Init_SSTable(SSTable &L){
    L.length=10;
    L.elem=(int *)malloc(L.length*sizeof(int));
    for(int i=1;i<=9;i++){
        scanf("%d",&L.elem[i]);
    }
}


int Binary_Search(SSTable L,int key){
    int low=1,high=L.length;
    while(low<=high){
        int mid=(low+high)/2;
        if(L.elem[mid]==key)return mid;
        else if(L.elem[mid]>key) high=mid-1;
        else low=mid+1;
    }
    return 0;
}


int main(){
    SSTable T;
    Init_SSTable(T);
    printf("输入关键字\n");
    int key;
    scanf("%d",&key);
    printf("位置为（0表示查找失败）：%d\n",Binary_Search(T,key));
}

总结：

1.折半查找只适用于有序顺序表