李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--二分查找算法
Leefs
2020-02-06 PM
1373℃
0条
# 数据结构和算法学习--二分查找算法 ### 一、二分查找 ``` 请对一个有序数组进行二分查找{1,8,10,89,1000,1234},输入一个数看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。 ``` ### 二、二分查找算法的思路 ![23.二分查找算法01.png][1] > 分析: > > 1. 1.首先确定该数组的中间的下标 > > mid=(left+right)/2 > > 2. 2.然后让需要查找的数findVal和arr[mid]比较 > > + **findVal>arr[mid]**:说明你要查找的数在mid的右边,因此需要递归的向右查找 > + **findVal
+ findVal==arr[mid]:说明找到,就返回 > > 3. 3.结束递归的条件 > > + 找到就结束递归 > + 递归完整个数组,仍然没有找到findVal,也需要结束递归 当left>right就需要退出 **代码实现** ``` 请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。 课后思考题: {1,8, 10, 89, 1000, 1000,1234} 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000. ``` ```java //注意:使用二分查找的前提是 该数组是有序的 public class BinarySearch { public static void main(String[] args) { int arr[] = {1,8,10,89,1000,1000,1234}; //int resIndex = binarySearch(arr,0,arr.length-1,1000); //System.out.println("resIndex="+resIndex); List
resIndexList = binarySearch2(arr,0,arr.length-1,1000); System.out.println("resIndexList="+resIndexList); } /** * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findVal 要查找的值 * @return 找到就返回该值的下标,没找到,就返回 -1 * */ public static int binarySearch(int[] arr,int left,int right,int findVal){ //当left > right时,说明递归整个数组,但是没找到 if(left>right){ return -1; } int mid=(left+right)/2; int midVal=arr[mid]; if(findVal > midVal){//向右递归 return binarySearch(arr,mid+1,right,findVal); }else if(findVal < midVal){ return binarySearch(arr,left,mid-1,findVal); }else{ return mid; } } public static List
binarySearch2(int[] arr, int left, int right, int findVal){ //当left>right时,说明递归整个过程,但是没有找到 if(left>right){ return new ArrayList
(); } int mid=(left+right)/2; int midVal=arr[mid]; if(findVal > midVal){//向右递归 return binarySearch2(arr,mid+1,right,findVal); }else if(findVal < midVal){//向 左递归 return binarySearch2(arr,left,mid-1,findVal); }else{ /*** * 思路分析 * 1. 在找到mid索引值,不要马上返回 * 2. 向mid索引值的左边扫描,将所有满足1000 的元素的下标,加入到集合ArrayList * 3. 向mid索引值的右边扫描,将所有满足1000 的元素的下标,加入到集合ArrayList * 4. 将ArrayList返回 * */ List
resIndexList = new ArrayList
(); //2. 向mid索引值的左边扫描,将所有满足1000 的元素的下标,加入到集合ArrayList int temp = mid - 1; while(true){ if(temp<0||arr[temp]!=findVal){ break; } //否则,就temp放入到resIndexList resIndexList.add(temp); temp-=1;//temp左移 } resIndexList.add(mid); //向mid索引值的右边扫描,将所有满足1000 的元素的下标,加入到集合ArrayList temp=mid+1; while(true){ if(temp > arr.length - 1 || arr[temp]!=findVal){ break; } //否则,就temp放入到resIndexlist resIndexList.add(temp); temp+=1;//temp右移 } return resIndexList; } } } ``` > 运行结果 ``` resIndexList=[4, 5] ``` [1]: https://lilinchao.com/usr/uploads/2020/02/258071563.png
标签:
数据结构和算法
,
查找
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://www.lilinchao.com/archives/554.html
上一篇
数据结构和算法学习--常用排序算法总结和对比
下一篇
数据结构和算法学习--插值查找算法
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
正则表达式
数据结构和算法
LeetCode刷题
Zookeeper
Eclipse
Sentinel
Elasticsearch
序列化和反序列化
Jquery
随笔
散列
Spark
CentOS
Quartz
国产数据库改造
NIO
GET和POST
nginx
HDFS
持有对象
FastDFS
Hive
JavaWeb
高并发
ajax
Yarn
栈
数据结构
工具
gorm
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞