查找算法相关代码

算法相关代码"/>

查找算法相关代码

SearchFunc.h

//
//  SearchFunc.hpp
//  FirstP
//
//  Created by 赫赫 on 2023/11/1.
//#ifndef SearchFunc_hpp
#define SearchFunc_hpp#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;#endif /* SearchFunc_hpp *///顺序查找表结构
//时间复杂度O(n)
typedef struct{int *elem;      //动态数组基址int TableLen;   //表长度
}SSTable;//顺序查找(哨兵方式，数据从下标1开始存，下标0的位置存放查找关键字，即“哨兵”)
int Search_Seq(SSTable st,int key);//折半查找，又称二分查找，仅适用于有序顺序表
//时间复杂度O(log(n))
int Binary_Search(SSTable st,int key);

SearchFunc.cpp

//
//  SearchFunc.cpp
//  FirstP
//
//  Created by 赫赫 on 2023/11/1.
//  查找算法代码#include "SearchFunc.hpp"//顺序查找(哨兵方式，数据从下标1开始存，下标0的位置存放查找关键字，即“哨兵”)
//时间复杂度O(n)
int Search_Seq(SSTable st,int key){st.elem[0]=key;int i;//从表尾开始向前查找for(i=st.TableLen;st.elem[i]!=key;i++);//如果i=0，那么就意味着没有查找到，否则返回数据存放下标return i;
}//折半查找，又称二分查找，仅适用于有序顺序表(默认升序)
//时间复杂度O(log(n))
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){high=mid-1;}else{low=mid+1;}}return -1;//表示没有找到元素
}