我所知道的十大常用算法之二分查找(非递归)
文章目录
前言需求
前面我们有一起分享学习过:二分查找算法
忘记了的同学小伙伴可以再点击看看,那么我们之前的方式是采用递归的方式
今天我们需要学习的是采用:非递归的方式完成二分查找算法
一、二分查找算法介绍
首先可以让我们回顾一下二分查找算法的一些特点,比如说:
是一种在有序数组中查找某一特定元素的搜索算法。
1.搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索结束
2.如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且重新开始从中间元素进行比较。
3.如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半
我们知道的时间复杂度为O(logn),即假设从[0-99]的队列中查找目标数30,则需要查询的步数最多为:7次(2^6 < n <2 ^ 7)
二、通过示例学习非递归方式实现
数组{1, 3, 8, 10, 11, 67, 100},编程实现二分查找,要求使用非递归的方式完成.
/**
* @param arr 待查找的数组
* @param target 需要查找的数
* @retum 返回找到的下标,没有则返回 -1
*/
public static int binarySearch(int[] arr,int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){
int mid = (left + right) /2 ;
if(arr[mid] == target){
return mid;
}else if (arr[mid] > target){
right = mid -1;
}else{
left = left + 1;
}
}
return -1;
}接下来我们查询数据:11 看看
public static void main(String[] args) {
int[] arr = {1, 3, 8, 10, 11, 67, 100};
int index = binarySearch(arr,11);
System.out.println("index =>" + index);
}
运行结果如下:
index =>4接下来我们查询数据:22 看看
public static void main(String[] args) {
int[] arr = {1, 3, 8, 10, 11, 67, 100};
int index = binarySearch(arr,22);
System.out.println("index =>" + index);
}
运行结果如下:
index => -1
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论