二分搜索算法是运用分治策略的典型例子。
基本思想:将n个元素分成大致相同的两半,取a[n/2]与x进行比较。如果x==a[n/2],则找到,算法终止。如果a[n/2]>x,则只要在数组的左半部分继续搜索x.如果x>a[n/2],则只要在数组的右半部分继续搜索。
算法简单实现如下:
//二分搜索法
public class BinarySearch
{
/* 采用二分搜索法在一个有序的数组中查找x元素
* 找到x时返回它在数组中位置,否则返回-1
*
*/
public static int binarySearch(int[] arr, int n, int x)
{
//n为数组元素个数,x为要查找元素
int left = 0, right = n - 1;
while (left <= right)
{
int middle = (left + right ) / 2;
if (arr[middle] == x) //找到元素x
{
return middle;
}
if (x > arr[middle])
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
return -1; //未找到
}
//测试
public static void main(String[] args)
{
int[] arr = {1, 2, 3, 4, 8, 10};
int index = BinarySearch.binarySearch(arr, 6, 1);
if (index == -1)
{
System.out.println("Not find");
}
else
{
System.out.println("Find it: index -> " + index);
}
}
}
分享到:
相关推荐
如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法。二分查找很好写,却很难写对,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码。 1、...
主要介绍了Java分治法与二分搜索算法,简单讲述了分治法与二分搜索算法的原理并结合java实例分析了二分搜索算法的实现与使用技巧,需要的朋友可以参考下
主要介绍了二分查找算法在C/C++程序中的使用示例,文中最后提到了使用二分查找法一个需要注意的地方,需要的朋友可以参考下
顺序查找、二分搜索(用移位代替除法)、红黑树、AVL 树、哈希 抱歉留了个 B+ 树的坑还没写完,学完数据库回来补上 在实现各个算法基础上,加入了算法运行时间比较以及搜索比较次数比较,从比较次数其实可以很清楚...
穷举搜索法.txt 符号图形.txt 简单数据库.txt 简单计算器.txt 简单逆阵.txt 线性顺序存储结构.txt 线索化二叉树.txt 绘制圆.txt 编随机数.txt 网络最短路径Dijkstra算法.txt 自我复制.txt 节点.txt ...
穷举搜索法.c 简单数据库.c 编程汉字问题.txt 编随机数.c 试题.C 递堆法.C ./单元加: erre2.c erre.c 数组完全单元.c 栈单元加.c ./字符: 单词倒转.c 反出字符.c 回文.c 字符串查找.c 字符编辑.c 字符编辑...
鉴于上诉各种要求,我们决定对购买的遥控小车进行简单改造,使用PC机已有的硬件条件编写软件来完成语音的输入,采集,处理和识别,以实现对小车的控制。 三、 解决思路与模块: 整个程序大致可划分为三个模块,其...
数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。数据挖掘通常与计算机科学有关,并通过统计、在线分析处理、情报检索、机器 学习、专家系统(依靠过去的经验法则)和模式识别等诸多方法来实现...
穷举搜索法.txt 符号图形.txt 简单数据库.txt 简单计算器.txt 简单逆阵.txt 线性顺序存储结构.txt 线索化二叉树.txt 绘制圆.txt 编随机数.txt 网络最短路径Dijkstra算法.txt 自我复制.txt 节点.txt ...
17.3.4 二分覆盖 17.3.5 单源最短路径 17.3.6 最小成本生成树 17.4 参考及推荐读物 第18章 分而治之 18.1 算法思想 18.2 应用 18.2.1 残缺棋盘 18.2.2 归并排序 18.2.3 快速排序 18.2.4 选择 18.2.5 相距最近的点对 ...
二分查找:二分查找基本代码 33搜索旋转排序数组, 81搜索旋转排序数组II 153寻找旋转排序数组中的最小值 154寻找旋转排序数组中的最小值 33,81,153,154 这四题的思路几乎一样 34排序数组找第一个和最后一个位置 4...
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过C语言程序设计的人士继续深造的理想读物,也可作为具有一定经验的程序设计人员巩固和提高编程水平,查阅相关算法实现和数据结构知识的参考...
算法和数据结构 家庭作业13-6-2018: 什么是算法? 什么是数据结构? Big O表示法是什么? 实现二进制搜索(SearchService)。 调整线性搜索(搜索文本)... 实现所有简单排序,线性和二进制搜索。 研究高级排序
基于MFC和STL平台的字符串类,可以实现在快速字符串搜索。 enum_display_modes_demo.zip enum_display_modes_src.zip 列出所有的显示模式并列表出来,通过单击列表来改变显示分辨率。 iconbutton_demo.zip ...
基于MFC和STL平台的字符串类,可以实现在快速字符串搜索。 enum_display_modes_demo.zip enum_display_modes_src.zip 列出所有的显示模式并列表出来,通过单击列表来改变显示分辨率。 iconbutton_demo.zip ...
基于MFC和STL平台的字符串类,可以实现在快速字符串搜索。 enum_display_modes_demo.zip enum_display_modes_src.zip 列出所有的显示模式并列表出来,通过单击列表来改变显示分辨率。 iconbutton_demo.zip ...
基于MFC和STL平台的字符串类,可以实现在快速字符串搜索。 enum_display_modes_demo.zip enum_display_modes_src.zip 列出所有的显示模式并列表出来,通过单击列表来改变显示分辨率。 iconbutton_demo.zip ...
基于MFC和STL平台的字符串类,可以实现在快速字符串搜索。 enum_display_modes_demo.zip enum_display_modes_src.zip 列出所有的显示模式并列表出来,通过单击列表来改变显示分辨率。 iconbutton_demo.zip ...