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语言运算符优先级列表(超详细)
每当想找哪个运算符优先级高时,很多时候总是想找的就没有,真让人气愤!现在,终于有个我个人觉得非常全的,分享给大家,欢迎拍砖! 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语言文件操作函数大全(超详细)
fopen(打开文件)相关函数 open,fclose表头文件 #include<stdio.h>定义函数 FILE * fopen(const char * path,const char * mode);函数说明 参数path字符串包含欲打开的文件路径及文件名,参数mode字符串则代表着流形态.mode有下列几种形态字符串:r 打开只读文件,该文件必须存在.r+ 打开可读写的文件,该文件必须存在.w 打开只写文件,若文件存在则文件长度清为0,即该文件内容会消失.若文件不存在则建立该文件.w
-
C++二分法在数组中查找关键字的方法
本文实例讲述了C++二分法在数组中查找关键字的方法.分享给大家供大家参考.具体如下: /* 此程序演示了二分法查找算法(针对按从小到大排列的数组)的实现. */ #include <iostream> using namespace std; /* 功能: 实现数组的二分法查找(只算法只适合按从小到大排列的数组) 返回值:关键字在数组中的下标, 返回-1表示未找到 a[]: 要搜索的数组 len: 数组元素个数 key: 要查找的关键字 */ int binSearch(int a[], in
-
C语言实现socket简单通信实例
本文实例讲述了C语言实现socket简单通信的方法,分享给大家供大家参考.具体实现方法如下: 服务器端代码如下: /* ============================================================================ Name : server.c Author : king Version : Copyright : Your copyright notice Description : Hello World in C, Ansi-st
-
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经典算法之二分查找法
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
-
java算法之二分查找法的实例详解
java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me
-
JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】
本文实例讲述了JavaScript数据结构与算法之检索算法.分享给大家供大家参考,具体如下: javascript数据结构与算法---检索算法(二分查找法.计算重复次数) /*只需要查找元素是否存在数组,可以先将数组排序,再使用二分查找法*/ function qSort(arr){ if (arr.length == 0) { return []; } var left = [];//存储小于基准值 var right = [];//存储大于基准值 var pivot = arr[0]; fo
-
javascript实现二分查找法实现代码
一般二分都用到int[]型上.....在js中可能会更灵活的用到a-z上,或者用到拼音...或者用到...... 不过值得深思的一个问题是,如果为了实现对拼音之类的二分查找.而经过如下流程是否值得: 1.对拼音排序,貌似代码量不小吧. 2.然后再二分查找.这又需要识别拼音的大小,貌似也不算太小吧. 找到结果的速度快了,可是别人下你的js文件速度慢多了,呵呵,到底舍弃谁. 下面的代码甚至可以10亿条,一样会很快找到,可是用遍例的模式创建那个数组...所以还是别尝试了.只是给个思路,下次我再来发个j
-
C#使用二分查找法判断指定字符的方法
本文实例讲述了C#使用二分查找法判断指定字符的方法.分享给大家供大家参考,具体如下: private int sort_init(ref string[] chars, string str) //数组初始化 { string[] temp = str.Split(' '); //temp. chars = new string[temp.Count()]; int ndx = 0; int last_empty_positon = 0; foreach (string ch in temp)
-
java数据结构之二分查找法 binarySearch的实例
java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.
-
js基本算法:冒泡排序,二分查找的简单实例
知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i
-
使用javascipt---实现二分查找法
复制代码 代码如下: <html><head><meta http-equiv="Content-Type" content="text/html;charset=utf-8"><script type="text/javascript"> //window.alert(Math.floor(5.7)); //向下取整 输出5 //二分查找法 数组必须是有序的 function binarySeac
-
浅谈选择、冒泡排序，二分查找法以及一些for循环的灵活运用
如下所示: import java.util.Arrays; //冒泡排序 public class Test { public static void main(String[] args) { int[] array = { 31, 22, 15, 77, 52, 32, 18, 25, 16, 7 }; // 冒泡 --> 两两比较 --> 提取出最大的数 在最后一位 //拿第一位和它后面的一位进行 两两比较 System.out.println(Arrays.toString(arra
-
查找算法之二分查找的C++实现
二分查找 二分查找算法,说白了就是在有序的数组里面给予一个存在数组里面的值key,然后将其先和数组中间的比较,如果key大于中间值,进行下一次mid后面的比较,直到找到相等的,就可以得到它的位置. 前提:线性表中的记录必须是关键字有序(通常从小到大),线性表必须采用顺序存储. 基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功:若给定值小于中间记录的关键字,则在中间记录的左半区继续查找:否则,在右半区查找.不断重复,直到查找成功或查找失败为止. #include<ios