文档章节

二分算法

空_明
 空_明
发布于 2014/03/20 01:22
字数 828
阅读 98
收藏 2
点赞 0
评论 0
public class demo{

	  /**
	  * 二分查找算法 
	    * 
	    * @param srcArray 有序数组 
	    * @param key 查找元素 
	    * @return key的数组下标,没找到返回-1 
	    */  
	    public static void main(String[] args) { 
	        int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};   
	        System.out.println(Search(srcArray, 0, srcArray.length - 1, 81)+"***");  
	    } 
	     
	    // 二分查找递归实现   
	    public static int Search(int srcArray[], int start, int end, int key) {   
	        int mid = (end - start) / 2 + start;   
	        if (srcArray[mid] == key) {   
	            return mid;   
	        }   
	        if (start >= end) {   
	            return -1;   
	        } else if (key > srcArray[mid]) {   
	            return binSearch(srcArray, mid + 1, end, key);   
	        } else if (key < srcArray[mid]) {   
	            return binSearch(srcArray, start, mid - 1, key);   
	        }   
	        return -1;   
	    } 
	     
	    // 二分查找普通循环实现   
	    public static int binSearch(int srcArray[], int key) {   
	        int mid = srcArray.length / 2;   
	        if (key == srcArray[mid]) {   
	            return mid;   
	        }   
	  
	        int start = 0;   
	        int end = srcArray.length - 1;   
	        while (start <= end) {   
	            mid = (end - start) / 2 + start;   
	            if (key < srcArray[mid]) {   
	               end = mid - 1;   
	            } else if (key > srcArray[mid]) {   
	                start = mid + 1;   
	            } else {   
	                return mid;   
	            }   
	        }   
	        return -1;   
	    } 
	}

二分查找

二分查找又称折半查找,它是一种效率较高的查找方法。

折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查找表中的数据元素必须有序。

点击放大图片

优点

     是比较次数少,查找速度快,平均性能好;

缺点

    是要求待查表为有序表,且插入删除困难。

因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

算法步骤描述

① 首先确定整个查找区间的中间位置 mid = ( left + right )/ 2

② 用待查关键字值与中间位置的关键字值进行比较;

  若相等,则查找成功

  若大于,则在后(右)半个区域继续进行折半查找

  若小于,则在前(左)半个区域继续进行折半查找

③ 对确定的缩小区域再按折半公式,重复上述步骤。

最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放。

折半查找算法举例

对给定数列(有序){ 3,5,11,17,21,23,28,30,32,50,64,78,81,95,101},按折半查找算法,查找关键字值为81的数据元素。

折半查找的算法讨论:

优点:ASL≤log2n,即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。

缺点:因要求有序,所以要求查找数列必须有序,而对所有数据元素按大小排序是非常费时的操作。另外,顺序存储结构的插入、删除操作不便利。

考虑:能否通过一次比较抛弃更多的部分(即经过一次比较,使查找范围缩得更小),以达到提高效率的目的。……?

可以考虑把两种方法(顺序查找和折半查找)结合起来,即取顺序查找简单和折半查找高效之所长,来达到提高效率的目的?实际上这就是分块查找的算法思想。












































© 著作权归作者所有

共有 人打赏支持
空_明
粉丝 32
博文 92
码字总数 71993
作品 0
东城
高级程序员
司机乘客匹配中的距离和最小问题

这个是在工作中遇到的一个实际的算法问题,问题描述如下,当前有m个司机,n个乘客,每个司机和每个乘客的距离由经纬度可以计算得到,如何匹配可以使其去接乘客的距离和最小?(只能一个司机接...

necther
05/03
0
0
二分图算法模板以及相关知识

说说二分图,其实图论的题难点不在用算法,难在如何建图,只有图建好了,剩下的就简单了,在这说说求二分图的算法,即匈牙利算法,其实一点都不难,也很好理解拿笔写写就行了. //板子, 直接套就行 //...

Anxdada
2017/06/22
0
0
每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述,就是任何实现某种功能的代码片...

爱吃西瓜的番茄酱
01/07
0
0
算法知识梳理(8) - 二分查找算法及其变型

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/12
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际...

dqcfkyqdxym3f8rb0
2017/11/24
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
0
0
二分查找(Binary Search)

1、定义 二分查找又称折半查找,它是一种效率较高的查找方法。 二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。 2、基本...

野渡书生
2016/04/28
15
0
从零基础学三分查找

转载请注明:http://www.cnblogs.com/ECJTUACM-873284962/ 今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章...

angel_kitty
2017/03/11
0
0
跟黄哥学python序列文章之python二分查找算法

跟黄哥学python序列文章之python二分查找算法 在计算机科学中,二分查找算法(binary search)、也称折半搜索(英语:half-interval search), 二分搜索法、二分搜索、二分探索,是一种在有...

黄哥Python培训
2016/04/05
231
0
[BZOJ2663][Beijing wc2012]灵魂宝石(二分+二分图匹配)

传送门 因为问题是单调的,R小肯定匹配的少,R大肯定匹配的多,所以一眼可以二分+二分图匹配。 难点就在要求最小值和最大值,最小值好求,但是最大值呢? 因为二分图匹配算法是求得最大匹配,...

cabi_zgx
03/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

TensorFlow 线性回归 拟合

用tf 对 一次函数进行拟合 效果 loss 简单实现如下 import tensorflow as tfimport numpy as npimport matplotlib.pyplot as plt# 保存显示数据plotdata = {"batchsize": [], "los...

阿豪boy
8分钟前
0
0
JupyterLab安装地图插件

JupyterLab安装地图插件 (本文所述软件还在发展之中,欢迎加入开源项目,提供建议、测试和开发。) 在Jupyter中进行数据分析时,往往需要将数据叠加到地图上。简单的可以利用matplotlib/ec...

openthings
17分钟前
0
0
Coding and Paper Letter(八)

资源整理 1 Coding: 1.Python项目,由Allen Downey撰写的Think Python第二版的LaTeX源代码和支持代码。 ThinkPython2 2.R语言包h3jsr,h3jsr使用V8的神奇力量通过其javascript绑定提供对Ube...

胖胖雕
26分钟前
0
0
skiplist跳跃表

插入删除log(N) TODO

梦想游戏人
27分钟前
1
0
利用世界杯,读懂 Python 装饰器

Python 装饰器是在面试过程高频被问到的问题,装饰器也是一个非常好用的特性, 熟练掌握装饰器会让你的编程思路更加宽广,程序也更加 pythonic。 今天就结合最近的世界杯带大家理解下装饰器。...

p柯西
40分钟前
0
0
Xshell登录阿里云服务器ECS

Xshell登录阿里云服务器ECS 1. 参考资料: 1). 《阿里云服务器怎么用?阿里云服务器使用教程》 链接:http://www.cr173.com/html/50758_1.html 2). eagle-zhang的CSDN博客《Xshell连接不上阿...

SuShine
50分钟前
1
0
IDEA中的HTTP Client Editor测试API

在前后端分离项目,前后端通过api进行通信。如果用postman免费版进行api测试的话,由于无法保存测试脚本到文件,不方便前端查看。 你可以选择付费版。也可以利用IDEA自带的HTTP Client Edito...

hutaishi
52分钟前
0
0
解决“只能通过Chrome网上应用商店安装该程序”的方法

摘要 : 最近有些用户反映某个Chrome插件在安装的时候,提示“只能通过Chrome网上应用商店安装该程序”,为了解决这一问题,Chrome插件网带来了相关的解决方法。 某些用户在Chrome插件网下载了...

沧海一刀
54分钟前
0
0
通过UNIX域套接字传递文件描述符

  传送文件描述符是高并发网络服务编程的一种常见实现方式。Nebula 高性能通用网络框架即采用了UNIX域套接字传递文件描述符设计和实现。本文详细说明一下传送文件描述符的应用。 1. TCP服务...

Bwar
57分钟前
0
0
python操作Excle

# -*- coding: utf-8 -*-from openpyxl import load_workbook, Workbook#index:第几个sheet页,第一个sheet页的index为0def readExcle(filename,index): # 加载excle文件 wb = l......

淺陌离殇
58分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部