C经典算法之二分查找法的示例分析

发布时间:2021-07-22 15:00:18 作者:小新
来源:亿速云 阅读:367

这篇文章主要介绍C经典算法之二分查找法的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

C经典算法之二分查找法

1.根据key查找所在数组的位置

#include <stdio.h>
/*
 key = 9;
 1 2 3 4 5 6 7 8
 arr 3, 4, 5, 7, 9 , 11, 21, 23
 low = 1  mid = (low + high)/2 = 4      high = 8;
 one   arr[mid] = 7 < 9;  so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
 two   arr[mid] = 11 > 9  so low = 5 ,   high = mid - 1 = 5 mid = 5;
 arr[mid] = 9 == key

 if(key = 10) low = mid + 1 > high

 */
int main(int argc, const char * argv[])
{
 int findByHalf(int arr[], int len, int key);

 int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
 int len = sizeof(arr)/sizeof(int);

 int index = findByHalf(arr, len, 88);

 printf("index = %d\n", index);
 return 0;
}

int findByHalf(int arr[], int len, int key){
 int low = 0;
 int high = len - 1;

 int mid ;


 while(low <= high){
  mid = (low + high) / 2;
  //右边查找
  if (key > arr[mid]) {
   low = mid + 1;
  //左边查找
  }else if (key > arr[mid]) {
   high = mid - 1;
  }else{
   return mid;
  }

 }
 return -1;
}

2.插入一个数,得到其所在数组的位置

#include <stdio.h>
/*
 key = 9;
 1 2 3 4 5 6 7 8
 arr 3, 4, 5, 7, 9 , 11, 21, 23
 low = 1  mid = (low + high)/2 = 4      high = 8;
 one   arr[mid] = 7 < 9;  so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
 two   arr[mid] = 11 > 9  so low = 5 ,   high = mid - 1 = 5 mid = 5;
 arr[mid] = 9 == key

 if(key = 10) low = mid + 1 > high

 */
int main(int argc, const char * argv[])
{
 int findByHalf(int arr[], int len, int key);

 int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
 int len = sizeof(arr)/sizeof(int);

 int index = findByHalf(arr, len, 88);

 printf("index = %d\n", index);
 return 0;
}

int insertByHalf(int arr[], int len, int key){
 int low = 0;
 int high = len - 1;

 int mid ;


 while(low <= high){
  mid = (low + high) / 2;
  //右边查找
  if (key > arr[mid]) {
   low = mid + 1;
  //左边查找
  }else if (key > arr[mid]) {
   high = mid - 1;
  }else{
   //如果arr[mid] == key
   //就把key插入到这个数的后面
   return mid + 1;
  }

 }
 //如果low > high 说明 key > arr[mid];
 //就把key插入到low对应的 这个数的位置
 return low;
}

以上是“C经典算法之二分查找法的示例分析”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!

推荐阅读:
  1. Java中的经典算法之选择排序(SelectionSort)
  2. c#之System.String的示例分析

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c语言

上一篇:linux下怎么自动备份MySQL数据并上传到FTP上

下一篇:PHP中有哪些连接数据库的方式

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》