上周末在ITEYE上看到一个标题‘在充足时间下,只有百分之二十程序员能成功完成的二分查找’,当时心想,对于算法虽然基础不是很精通,但是基础的还没问题,抱着好奇心点了进去,原来是一个编程挑战,题目当然是实现二分查找,还有一个附属条件是当有多个值相同时,返回最小下标,看看时间,一个小时呢,心想应该很快能够实现的,当然首先想到是写一个递归算法,写递归算法首先的是要确定出口,当时很自然的觉得应该是开始下标应该小于等于结束下标,于是就开始实现了,结果到后来发现查找数组里有的数据时没有问题,查找没有的值时会出现栈溢出,发觉自己还是心理素质不够好,当时就不淡定了,想着自己的想法应该没有问题,后来时间快到了,就勉强提交了只能查找存在数值的版本上去。最近这周任务比较紧,也就没来得及细细思索这个问题,不过一直挂在脑子里,今天下午终于有点时间,于是挤出来重新实现了一遍,发现问题就在递归出口上,其实当时也应该想到栈溢出的一种可能就是递归无出口的问题,于是最终去掉了首尾下标相等的条件,也就实现了查找了,当然重复值返回最小下标应该是比较简单了,在找到查找的值时再向前来一次二分查找就可以了。
package com.johnson.algo;
public class BinarySearch {
public static int search(int[] arr, int start, int end, int val) {
if (start < end) {
int mid = start + ((end - start) >> 1);
if (val == arr[mid]) {
int k = -1;
//这里再进行一次二分查找即可实现返回重复值的最小下标
if ((k = search(arr, start, mid, val)) != -1) {
return k;
}
return mid;
} else if (val < arr[mid]) {
return search(arr, start, mid, val);
} else {
return search(arr, mid + 1, end, val);
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = { 0, 3, 4, 6, 11, 11, 11, 87 };
System.out.println(search(arr, 0, arr.length - 1, 11));
}
}
分享到:
相关推荐
折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)
二分查找算法,二分查找算法课件,二分查找算法PPT
二分查找_测试
二分查找算法
VB 二分查找 VB 二分查找 VB 二分查找
二分查找 C语言语言源代码 用递归写的 C语言入门经典代码 值得收藏
简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。 程序的关键点主要有两点: 1. 如何在页面上表示出查找程序的运行过程。 2. 如何将排序程序的运行...
二分查找ppt
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
//文件名:exp9-2.cpp #include #define MAXL 100 //定义表中最多记录个数 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key;
C++ 二分查找法
二分查找动画,保准您一看就能领会,不需要再看繁文,助您学习
这里是二分查找的C#实现,这里是二分查找的C#实现,
C++ 二分查找的实现 C++ 二分查找的实现 C++ 二分查找的实现
二分查找基本教程,适合入门noip的学生,非常简单的讲述了二分查找的基本算法,适合入门!
实现二分查找 杨辉三角 二维一维数组便利
//二分查找 #include const int MAXN=10010; using namespace std; //二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则...
算法分析与设计-实验二 二分查找实验报告
文件读出数组进行选择排序和二分查找文件读出数组进行选择排序和二分查找java实现