看到一篇很有意思的文章就动手解决了一下问题。。。觉得有点意思~正逢毕业VS求职VS面试VS....高峰期,各种潮涌。
《编程珠玑》中的两句话:
-
尽管给了那么充裕的时间,只有大约10%的专业程序员能够写出正确的二分查找。
-
尽管第一个二分查找程序于1946年就公布了,但是第一个没有bug的二分查找程序在1962年才出现。
当时看到这的时候,我觉得有点夸张。这里不去讨论是否真的花了20年才人们才写出正确的代码,但这两句话至少告诉我们,不要小看二分搜索。
确实,写过bsearch的人都知道,迭代的出口很难在短时间内想清楚(反正我经常糊涂)。当然,常规的二分搜索大家现在基本都能写了,(写过这么多次,背也背下来了),但能写出来不代表真正理解了二分搜索。比如我们可以改动一下原型:从一个有序数组中找到大于x且最接近x的数。
说白了就是二分搜索,但是迭代的出口是什么的问题?
一、二分查找算法的原型JAVA代码表示
//传统二分搜索 PS:a数组中的值从小到大排列,找到目标X则返回下标值,未找到则返回-1
public static int bsearch(int[] a, int x) {
int l=0,h=a.length -1 ;
int m;
while(h>=l) {
m=(l+h)/2;
if(a[m] ==x) {
return m;
} else if(a[m] <x){
l=m+1 ;
} else {
h=m-1 ;
}
}
System.out.println("l:"+l+" h:"+h);
return -1 ;
}
考虑一下要查找的元素不在序列中的情况:函数会返回-1,那l和h分别指向什么呢?
可以证明:l指向大于x的第一个元素,r指向小于x的第一个元素。(为什么?迭代的最后一步必然是l和h指向同一元素,然后为什么会变得比h大呢?想想就明白了)
二、变形1
//功能简介: 在有序数组中查找比x大但是最接近x的数
//二分搜索 PS:a数组中的值从小到大排列,找到目标X则返回下标值,未找到则返回-1
public static int bsearch_more(int[] a, int x) {
int l=0,h=a.length -1 ;
int m;
while(h>=l) {
m=(l+h)/2;
if(a[m] ==x) {
return (m+1)>a.length-1?-1:m+1;
} else if(a[m] <x){
l=m+1 ;
} else {
h=m-1 ;
}
}
System.out.println("l:"+l+" h:"+h);
return l ;
}
三、变形2
//功能简介: 在有序数组中查找比x小但是最接近x的数
//二分搜索 PS:a数组中的值从小到大排列,找到目标X则返回下标值,未找到则返回-1
public static int bsearch_less(int[] a, int x) {
int l=0,h=a.length -1 ;
int m;
while(h>=l) {
m=(l+h)/2;
if(a[m] ==x) {
return (m-1)<0?-1:m-1;
} else if(a[m] <x){
l=m+1 ;
} else {
h=m-1 ;
}
}
System.out.println("l:"+l+" h:"+h);
return h ;
}
附:主函数测试代码JAVA表示
public static void main(String[] args) {
// TODO Auto-generated method stub
//传统二分搜索
int[] a = {1,4,7,9,10,17,20} ;
int sign = bsearch(a,11) ;
System.out.println(sign);
sign = bsearch_more(a, 18) ;
System.out.println(a[sign]);
sign = bsearch_less(a, 5) ;
System.out.println(a[sign]);
}
分享到:
相关推荐
IND = BSEARCH(VEC, VAL, TOL) 返回等于VAL 的 VEC 元素的索引 VEC 必须按升序排序(1、2、3 等) TOL > 0 表示 Y = X +/- 匹配的 TOL 计数 TOL = 0表示搜索精确匹配 TOL = -1 表示搜索最接近 VAL 的单个元素
C语言中可以用bsearch()实现二分查找。同qsort()一样,bsearch()也包含在库中,且同样要自定义比较子函数。
c语言词典结构体匹配法,qsort与bsearch
1、讲解C语言标准函数qsort快速排序的功能和应用; 2、讲解C语言标准函数bsearch二分查找的功能和应用;
用于二进制搜索排序文件中以搜索键开头的行的实用程序。 NAME: bsearch - utility for binary searching a sorted file for lines that start with the search key USAGE: bsearch [options] SEARCH_KEY ...
学习结构体排序查找以及链表的使用#include #include #include struct student { int num; double score; char name[100]; struct student *next; }; int cmp(const void *a,const void *b) { struct student *...
The bsearch() function searches an array of nmemb objects, the initial member of which is pointed to by base, for a member that matches the object pointed to by key. The size of each member of the ...
java.selectSort-bSearch 通过对ArrayList 的选择进行排序,并在排序后的数组中对键进行二进制搜索。
BSearch 本程序是使用Qt开发的文件搜索及文本内容搜索软件,支持Windows、Linux、Mac系统 .zip 基于Qt的系统项目开发 课程设计 毕业设计 供参考 源代码+说明 基于Qt的系统项目开发 课程设计 毕业设计 供参考 源...
这里提供三种方法来判断一个字符串中是否包括我们定义好的词,这比较适合于在留言,评论等地址进行关键词过滤,实例代码如下: 复制代码 代码如下:$crud = array(‘中国|||我国|||大地’, ‘kelon|||lerke|||sb’, ...
网络与通信:数据传输、信号处理、网络协议、网络与通信硬件、网络安全网络与通信是一个非常广泛的领域,它涉及到计算机科学、电子工程、数学等多个学科的知识。 云计算与大数据:数据集、包括云计算平台、大数据...
bsearchBrief 简介WASM built RustJieba, make in browser Chinese search possible!使用了rust编译的jieba中文分词,使得可以在浏览器中实现中文分词以及最重要的是使用了中文的搜索Example 例子使用说明Makefile中...
#搜索用于数组查找和掩码的快速 C-MEX 假设您需要屏蔽大型数组的索引`` argmin = find(x>=y, 1, 'first'); argmax = find(x<=y, 1, 'last'); maskedArray = x(argmin:argmax); `` 如果数组是预先排序的(例如,...
本文实例讲述了PHP基于二分法实现数组查找功能。...function bsearch_r($v, $arr, $low, $high){ if ($low > $high) {// 先判断结束条件 return -1; } $i = intval(($high + $low)/2); if ($arr[$i] > $v
在数据向量 'x' 中对向量 'var' 中指定的值进行二分搜索。 数据必须按升序或降序预先排序。 如果有多个具有相同值的数字,则无法预测函数的行为方式。 返回搜索到的数字的索引值。 如果 'var' 中的值超出 'x' 的...
var bsearch = require ( 'binary-search-bounds' ) //Create a list of triangles defined by indexed faces var triangles = [ [ 1 , 0 , 2 ] , [ 2 , 1 , 3 ] , [ 3 , 4 , 5 ] , [ 5 , 6 , 7 ] ] //Sort ...
memchr(在某一内存范围中查找一特定字符) 38 5.7 38 memcmp(比较内存内容) 38 5.8 39 memcpy(拷贝内存内容) 39 5.9 40 memmove(拷贝内存内容) 40 5.10 40 memset(将一段内存空间填入某值) 40 5.11 40 ...
本书内容全面、翔实,是学习C++编程语言的广大学生的一部有用的工具书,也是对C++感兴趣的读者的必备参考书。 第一部分 C++基础:C子集 第1章 C语言概述 1.1 C语言的起源和历史 1.2 C语言是中级语言 1.3 C语言是...
matlab开发-Binarysearch。bsearch对已排序的数组执行二进制搜索