概念: 二分查找算法只适合从一个有序序列(如果一个列表不是有序序列,我们可以先把它排序成有序序列)中进行查找某个值, 比如有序的数字序列或者字母序列.
注意: 二分查找运行的时间复杂度为 O(log2N)
二分查找法(非递归) 的思路:
在一个有序序列arr中查找目标值targetValue, 二分查找法的算法思路非常简单,就是比较targetValue和有序序列中间这个元素的值middleValue
1. 如果 targetValue < middleValue, 那么意味着targetValue在左半部分,那么现在只需要在左半部分中进行查找, 对左半部分再进行这样的二分查找
2. 如果targetValue = middleValue, 那么找到了,返回middleValue的位置即可
3. 如果targeValue > middleValue, 那么意味着targetValue在右半部分,那么现在只需要在右半部分中进行查找,对右半部分再次进行这样的二分查找
解题的代码如下:
public int binarySearch(int[] arr, int targetValue)
标签:二分,middleValue,递归,算法,查找,序列,targetValue From: https://www.cnblogs.com/wphl-27/p/17151665.html