Debug客栈
做一个爱分享的程序猿
Debug客栈
数据结构 折半查找法

算法原理

先确定待查记录所在的范围(区间),然后逐步缩小范围指导找到或找不到该记录为止。

算法性能

时间复杂度: log 2 n + 1
平均查找长度: log 2 n + 1 – 1

注意事项

  • 折半查找法必须为有序数列。
  • 可以是逆序的,但是必须得提前定义遍历对比对象。

算法实现

include "stdio.h"
//折半查找函数 
int binarySearch(int a[], int n, int key){
  //定义数组的第一个数 
  int low = 0;
  //定义数组的最后一个数
  int high = n-1;
  //定义中间的数值
  int mid;
  //存放中间的数值的变量
  int midVal; 
  //当左边的值小于等于右边的值的时候 
  while(low <= high){
      mid    = (low + high)/2;
      midVal = a[mid];

      //如果中间值小于用户查找到的数值,最低的数字到中间数值+1位置上 
      if(midVal < key){
          low = mid + 1;
      }else if(midVal > key){
      //如果中间值大于用户查找到的数值,最高的数字到中间数值-1位置上 
          high = mid - 1;
      }
      else
          return mid;   
  }
  return -1;    
}

int main(){
  int i, val, ret;
  int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  //打印数组
  for(i=0; i<10; i++)
      printf("%d \t", a[i]);

  printf("\n请你输入你要进行查找的元素\n");
  scanf("%d", &val);

  ret = binarySearch(a, 10, val);

  if(ret == -1){
      printf("查找失败!\n");
  } else{
      printf("查找成功!\n");
  }

  return 0;
} 
赞赏
本文链接:https://www.debuginn.cn/201.html
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可,转载请保留此文章链接
相关链接: Debug客栈  |  Debug客栈引导页  |  加入交流群  |  赞助本站  |  博主微博  |  博主推特  |  音乐下载器
社会主义核心价值观: 富强、民主、文明、和谐、自由、平等、公正、法治、爱国、敬业、诚信、友善

发表评论

textsms
account_circle
email

Debug客栈

数据结构 折半查找法
算法原理 先确定待查记录所在的范围(区间),然后逐步缩小范围指导找到或找不到该记录为止。 算法性能 时间复杂度: log 2 n + 1 平均查找长度: log 2 n …
扫描二维码继续阅读
2017-11-18