首页 > 编程语言 >【算法】二分查找算法 (非递归)

【算法】二分查找算法 (非递归)

时间:2023-02-24 15:35:09浏览次数:42  
标签:二分 middleValue 递归 算法 查找 序列 targetValue

概念:  二分查找算法只适合从一个有序序列(如果一个列表不是有序序列,我们可以先把它排序成有序序列)中进行查找某个值, 比如有序的数字序列或者字母序列.  

注意: 二分查找运行的时间复杂度为 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

相关文章