查找算法之顺序查找和二分查找

1.顺序查找

基本思想：从数据结构线性表一端开始，顺序扫描，依次将扫描到的关键字值与给定key相比较，若相等则表示查找成功 ；若扫描结束仍没有找到关键字等于key值的结点，表示查找失败。
顺序查找适合于存储结构为顺序存储或链接存储的线性表。

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;

const int maxn = 110;  
int arr[maxn];

int SequenceSearch(int arr[],int key, int n);

int main(){
 int n,key;
 printf("请输入元素的个数:\n"); 
 scanf("%d",&n);
 
 printf("请输入数组中的元素:\n");
 for(int i=0; i<n; i++){
  scanf("%d", &arr[i]);
 }
 
 printf("请输入要查找的值: ");
 scanf("%d", &key);
 
 int k = SequenceSearch(arr, key, n);
 
 if(k != -1)  printf("该值在数组下标为%d的位置", k);
 else    printf("该值不存在！"); 
    
 return 0;
}

int SequenceSearch(int arr[],int key, int n){
 int flag = 0;
for(int i=0; i<n; i++){
  if(arr[i] == key){
   flag =1;
   return i;
  }
 }
 
if(flag == 0) 
  return -1;
}

编译运行结果如图所示：

2.二分查找

基本思想：二分查找也称折半查找，中间结点将整个有序表分成两个子表，先将中间结点的关键字与给定的key值进行比较，若相等则查找成功；若不相等，则比较key值与中间结点关键字的大小，若key值小于中间结点关键字值，就继续在左边的字表进行二分查找，反之，在右边的字表进行二分查找。递归进行，直到查找到或查找结束发现表中没有这样的结点。

二分查找的表必须是有序的，如果是无序的需要进行排序；二分查找是一棵二叉排序树，每个根节点的值都大于左子树的所有结点的值，小于右字数所有结点的值。

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 110;  
int arr[maxn];

int BinarySearch(int arr[],int key, int n);

int main(){
int n,key; //元素个数，查找的值

printf("请输入元素的个数:\n"); 
scanf("%d",&n);

printf("请输入数组中的元素:\n");
 for(int i=0; i<n; i++){
  scanf("%d", &arr[i]);
 }
 
printf("请输入要查找的值: ");
scanf("%d", &key);

sort(arr, arr+n);  //排序函数 
int k = BinarySearch(arr, key, n);
if(k != -1)  printf("该值存在！");
    else    printf("该值不存在！"); 
    
    return 0;
 
}

int BinarySearch(int arr[], int key, int n){
 int low = 0, high = n-1;
 while(low <= high){
  
 int mid = (low +high)/2; //找出序列的中间点
 
 if(arr[mid] == key)  return mid;
 else if(arr[mid]> key) high = mid -1;
 else low = mid+1; 
 
 }
 return -1;
 
}

编译运行的结果如图所示：

参考文章