C++二分法在数组中查找关键字的方法
本文实例讲述了C++二分法在数组中查找关键字的方法。分享给大家供大家参考。具体如下:
/* 此程序演示了二分法查找算法(针对按从小到大排列的数组)的实现。 */ #include <iostream> using namespace std; /* 功能: 实现数组的二分法查找(只算法只适合按从小到大排列的数组) 返回值:关键字在数组中的下标, 返回-1表示未找到 a[]: 要搜索的数组 len: 数组元素个数 key: 要查找的关键字 */ int binSearch(int a[], int len, int key) { int i = len / 2; int ii = 0; if(len < 1) return -1; if((key > a[i]) && (len - i > 0)) { ii = binSearch(a+i+1, len - i - 1, key); // 在后半段数组中查找 if(ii != -1) return ii + i + 1; // 加上数组前半段的长度 else return -1; } else if(key < a[i] && i > 0) // 在前半段数组中查找 return binSearch(a, i, key); else if(key == a[i]) return i; // 返回关键字在数组中的下标 else return -1; // 未在数组中找到关键字 } int main() { int a[] = {2, 4, 5, 20, 24, 35, 66, 78, 98}; int len = sizeof(a) / sizeof(int); int i, key = -1; while(1) { cin>>key; i = binSearch(a, len, key); printf("%d\n", i); if(key > 100) break; } return 0; }
希望本文所述对大家的C++程序设计有所帮助。
相关推荐
-
C语言运算符优先级列表(超详细)
每当想找哪个运算符优先级高时,很多时候总是想找的就没有,真让人气愤!现在,终于有个我个人觉得非常全的,分享给大家,欢迎拍砖! C语言运算符优先级 优先级 运算符 名称或含义 使用形式 结合方向 说明 1 [] 数组下标 数组名[常量表达式] 左到右 -- () 圆括号 (表达式)/函数名(形参表) -- . 成员选择(对象) 对象.成员名 -- -> 成员选择(指针) 对象指针->成员名 -- 2 - 负号运算符 -表达式 右到左 单目运算符 ~ 按位取反运算符 ~表达式 ++ 自增运算符 +
-
c语言冒泡排序法代码
总在写 总在错, 面试也还忘记 学习就是这么个过程, 温故才知新, 望自己谨记 忘记不要紧 复习就好 //排序是有很多种方法的 ,完成从小到大的排列 复制代码 代码如下: #include <stdio.h>void sort(int *a,int len){int i=0; int j; int t; for(i=0;i<len;i++) { for(j=0;j<len-i-1;j++) { if(a[j]>a[
-
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
-
C语言文件操作函数大全(超详细)
fopen(打开文件)相关函数 open,fclose表头文件 #include<stdio.h>定义函数 FILE * fopen(const char * path,const char * mode);函数说明 参数path字符串包含欲打开的文件路径及文件名,参数mode字符串则代表着流形态.mode有下列几种形态字符串:r 打开只读文件,该文件必须存在.r+ 打开可读写的文件,该文件必须存在.w 打开只写文件,若文件存在则文件长度清为0,即该文件内容会消失.若文件不存在则建立该文件.w
-
C语言/C++中如何产生随机数
C语言/C++怎样产生随机数:这里要用到的是rand()函数, srand()函数,和time()函数. 需要说明的是,iostream头文件中就有srand函数的定义,不需要再额外引入stdlib.h;而使用time()函数需要引入ctime头文件. 使用rand()函数获取一个随机数如果你只要产生随机数而不需要设定范围的话,你只要用rand()就可以了:rand()会返回一随机数值, 范围在0至RAND_MAX 间.RAND_MAX定义在stdlib.h, 其值为2147483647. 例子
-
C语言实现socket简单通信实例
本文实例讲述了C语言实现socket简单通信的方法,分享给大家供大家参考.具体实现方法如下: 服务器端代码如下: /* ============================================================================ Name : server.c Author : king Version : Copyright : Your copyright notice Description : Hello World in C, Ansi-st
-
C++二分法在数组中查找关键字的方法
本文实例讲述了C++二分法在数组中查找关键字的方法.分享给大家供大家参考.具体如下: /* 此程序演示了二分法查找算法(针对按从小到大排列的数组)的实现. */ #include <iostream> using namespace std; /* 功能: 实现数组的二分法查找(只算法只适合按从小到大排列的数组) 返回值:关键字在数组中的下标, 返回-1表示未找到 a[]: 要搜索的数组 len: 数组元素个数 key: 要查找的关键字 */ int binSearch(int a[], in
-
JavaScript使用二分查找算法在数组中查找数据的方法
本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一
-
php实现在多维数组中查找特定value的方法
本文实例讲述了php实现在多维数组中查找特定value的方法.分享给大家供大家参考.具体如下: 最近做项目,需要从多维数组中查找是否含有特定的key和其对应特定的value,并清除该条数据,比如: $arr = array( //为了看的方便,数组表达形式不对 0=>array(id =>1,name =>"li") 1=>array(id =>2,name =>"na") 2=>array(id =>3,name =
-
php在数组中查找指定值的方法
本文实例讲述了php在数组中查找指定值的方法.分享给大家供大家参考.具体如下: php中有两个函数可以判断数组中是否包含指定的值,分别是:array_search($value, $array)和in_array($value, $array),array_search可以找出指定的值在数组中出现的位置,in_array函数只判断数组中是否存在指定的值,返回bool值 <?php $array = array("Perl", "PHP", "Java
-
JS查找数组中重复元素的方法详解
本文实例讲述了JS查找数组中重复元素的方法.分享给大家供大家参考,具体如下: JS的数据类型有一个数组.今天我们就来谈谈对数组的一种处理.相信很多人都遇到过从数组中查找出不重复的元素,但是我遇到的却是从数组中查找出重复的元素. 从js数组中查找出不重复的元素的方法有很多,下面就给大家列举一个: <!DOCTYPE html> <html> <body> <script> Array.prototype.deleteEle=function(){ var ne
-
Python实现在某个数组中查找一个值的算法示例
第一种算法思路: 第一步:随机出来一个数组的下标 第二步:判断下标对应的值是否等于被查找的值,是的话终止,已找到,否的话转第三步. 第三步:判断是否随机完数组的所有下标,是的话终止,没找到,否的话转第一步. 代码如下: #本程序的功能是在字典中查找存在某个值 import random di = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6} key = 2 di1 = {} while True: tmp = random.choice(di.keys()) #随机
-
Linux日志中查找关键字及其前后的信息实例方法
在日常工作中,我们经常需要查看日志,比如可以通过 tail 命令实时查看日志,也可以通过 cat 等命令查看日志信息. 但现在我们要讨论的是,如何从日志中通过关键字过滤出我们想要的内容,方法有多种,今天我们主要以 cat 命令来进行学习. 假设存在日志文件 hrun.log,查询的关键字为"新增用户": 根据关键字查看日志 cat hrun.log | grep "新增用户" 根据关键字查看后10行日志 cat hrun.log | grep "新增用户&
-
C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)
[LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity
-
Java C++解决在排序数组中查找数字出现次数问题
目录 1.题目 2.思路 3.c++代码 4.java代码 1.题目 统计一个数字在排序数组中出现的次数. 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 提示: 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 nums 是一个非递减数组 -10^9 <= target &l
-
JS简单去除数组中重复项的方法
本文实例讲述了JS简单去除数组中重复项的方法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html lang="zh-cn"> <head> <meta charset="UTF-8"> <title></title> </head> <body> <script> var arr = ["aaa","bb
随机推荐
- Windows Server 2008 R2和2012中PHP连接MySQL过慢的解决方法
- java自定义日志输出文件(log4j日志文件输出多个自定义日志文件)
- 微信JSSDK多图片上传并且解决IOS系统上传一直加载的问题
- 捕获键盘事件(且兼容各浏览器)
- 深入解析fsockopen与pfsockopen的区别
- 无限级别菜单的实现
- js用正则表达式控制价格输入实现代码
- 深入浅析C语言中堆栈和队列
- C#自定义RSA加密解密及RSA签名和验证类实例
- node.js require() 源码解读
- Css Reset(复位)方法整理第1/3页
- JS随机排序数组实现方法分析
- android图像绘制(六)获取本地图片或拍照图片等图片资源
- js如何编写简单的ajax方法库
- 配置 SQL Server 2005 以允许远程连接的方法
- 使用 jQuery 实现表单验证功能
- 模拟用户点击弹出新页面不会被浏览器拦截
- javascript实现的颜色块滑动的动态效果
- Android仿微信发表说说实现拍照、多图上传功能
- Windows下ftp操作常识问题集锦