public class BinSearch1st { Random random = new Random(); /** * 二分查找,找到s的下标,如果没有返回-1 * @param arr * @param s * @return */ public int bsearch(int[] arr, int s) { int left = 0; int right = arr.length - 1; int cur = 0; while (left <= right) { cur = (left + right) >>> 1; if (arr[cur] > s) { right = cur - 1; } else if (arr[cur] < s) { left = cur + 1; } else { return cur; } } return -1; } /** * 找到第一个s的下标,如果没有返回-1 * @param arr * @param s * @return */ public int search(int[] arr, int s) { int leftM = 0; int left = 0; int right = arr.length - 1; int cur = 0; while (left <= right) { cur = (left + right) >>> 1; if (arr[cur] > s) { right = cur - 1; } else if (arr[cur] < s) { left = cur + 1; leftM = left; } else { if (arr[leftM] == arr[cur]) {//这个地方容易被忽略 return leftM; } else if (leftM < cur && arr[leftM] < arr[cur] && left < right) { right = cur; } else { return cur; } } } return -1; } @Test public void test() { int len = 10 + random.nextInt(100); int[] arr = new int[len]; for (int i=0; i<len; i++) { arr[i] = random.nextInt(len); } Arrays.sort(arr); int s = arr[random.nextInt(len)]; int i = search(arr, s); int j = 0; for (; j<len; j++) { if (arr[j] == s) { break; } } System.out.println(Arrays.toString(arr)); System.out.println(i + " : " + arr[i] + " : " + s + " : " + j); Assert.assertEquals(j, i); int bs = bsearch(arr, s); Assert.assertEquals(s, arr[bs]); s = len; i = search(arr, s); bs = bsearch(arr, s); Assert.assertEquals(-1, i); Assert.assertEquals(-1, bs); } public static void main(String[] args) { BinSearch1st b = new BinSearch1st(); for (int i=0; i<100; i++) b.test(); } }
相关推荐
c 二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法...
C语言实现的二分法快速查找|二分法排序|二分法查找C#
二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
二分法查找法
二分法查找第一个不为0 bit 使用代码提交
一维数组应用 ——二分法查找 目录 课程导入 1 清楚并牢记二分法的实现条件 ...步骤3:如果key值小于中间项值,则在前半段(high=mid-1)中以二分法继续查找。 步骤4:如果key值大于中间项值,则在后半段(low=mid+1
二分法查找 (源码 C Java)
二分法查找和顺序查找 排序后二分法
给定的表中用二分法查找指定数 给定的表中用二分法查找指定数 给定的表中用二分法查找指定数
使用二分法查找的MATLAB程序编写,方便刚接触MATLAB的同学分享学习。
二分法查找第一个不为0 bit 文章中使用代码提交
一个二分法查找的图形演示程序,C++,一个二分法查找的图形演示程序,一个二分法查找的图形演示程序
题目要求演示二分法查找过程,...设计思想为用两个数组实现,一个用于存数据另一个用来存箭头。只要存箭头的下标于每次查找的数的下标相等就可以实现,难点在于如何把数得下标与箭头下标连在一起并修改箭头的所在位置。
写出二分法查找算法函数实现。
二分法数据查找C语言实现,只有10%程序员能正确实现二分查找算法--http://news.csdn.net/a/20100423/218099.html
易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar ...
C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,
精简算法 二分法查找数组 算法精简查找效率高!
易语言有序二分法查找源码,有序二分法查找,算法_二分法