java 二分法查找数组中目标值

本文主要是介绍java 二分法查找数组中目标值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、需求

在有序数组内，查找值target。如果找到返回索引，如果找不到返回-1。

二、算法思想

二分查找又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查值比较，
如果中间位置的值比待查值大，则在前半部分循环这个查找的过程，
如果中间位置的值比待查值小，则在后半部分循环这个查找的过程。
直到查找到了为止，否则序列中没有待查的值。

三、使用两种方式实现

public class BinarySearch {private int[] arrays;public BinarySearch(int[] arrays) {this.arrays = Arrays.stream(arrays).sorted().toArray();}/*** 二分查找平衡版* 1.左闭右开的区间，start指向的可能是目标，而end指向的不是目标* 2.不在循环内找出，等范围内只剩i时，退出循环，在循环外比较a[i]与target* 3.循环内的平均比较次数减少了* 4。时间复杂度Θ(log(n))* @param target* @return 查找到的索引，没找到则返回-1*/public int binarySearchByBalance(int target) {int start=0,end=arrays.length;while(1<end - start){int mid=(end +start)>>>1;//无符号右移,避免超过int最大值if(target<arrays[mid]){end = mid;}else {start = mid;}}if(target == arrays[start]){return start+1;}return -1;}/*** 二分查找基础版【非递归二分法查找目标值索引】* start和end 不仅是索引，而且指向的元素参与运算。左闭右闭的原则* @param target 目标值* @return 查找到的索引，没找到则返回-1*/public int searchBinary(int target){int start=0,end = this.arrays.length-1;//L次，元素在最左边找 L次，元素在最右边找 2*L 次。while(start<=end){int middle = (start +end) >>> 1;//无符号右移,避免超过int最大值if(arrays[middle]==target){return middle+1;} else if(arrays[middle]<target) {//如果目标值大于中间值则向右查找start = middle+1;}else {//如果目标值大于中间值则向左查找end = middle-1;}}return -1;}}

四、测试类

public class TestSearch {@Test@DisplayName("binarySearch 找到")public void test1() {int[] array = {1, 3, 4, 6, 8, 10, 12, 23, 66, 77, 88, 100};BinarySearch mySearch_binary = new BinarySearch(array);Assert.assertEquals(1, mySearch_binary.binarySearchByBalance(1));Assert.assertEquals(2, mySearch_binary.binarySearchByBalance(3));Assert.assertEquals(3, mySearch_binary.binarySearchByBalance(4));Assert.assertEquals(4, mySearch_binary.binarySearchByBalance(6));Assert.assertEquals(5, mySearch_binary.binarySearchByBalance(8));Assert.assertEquals(6, mySearch_binary.binarySearchByBalance(10));Assert.assertEquals(7, mySearch_binary.binarySearchByBalance(12));Assert.assertEquals(8, mySearch_binary.binarySearchByBalance(23));Assert.assertEquals(9, mySearch_binary.binarySearchByBalance(66));Assert.assertEquals(10, mySearch_binary.binarySearchByBalance(77));Assert.assertEquals(11, mySearch_binary.binarySearchByBalance(88));Assert.assertEquals(12, mySearch_binary.binarySearchByBalance(100));}@Test@DisplayName("binarySearch 没找到")public void test2() {int[] array = {1, 3, 4, 6, 8, 10, 12, 23, 66, 77, 88, 100};BinarySearch mySearch_binary = new BinarySearch(array);Assert.assertEquals(-1, mySearch_binary.binarySearchByBalance(9));Assert.assertEquals(-1, mySearch_binary.binarySearchByBalance(11));}

若大家有疑问或是更好方式，可以留言讨论。

这篇关于java 二分法查找数组中目标值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---