Java中的二分查找
二分查找:(折半查找)
前提:数组必须是有序的。
思想:每次都猜中间的那个元素,比较大或者小,就能减少一半的元素。
思路:A:定义最小索引,最大索引。
B:比较出中间索引
C:拿中间索引的值和要查找的元素进行比较
相等:就直接返回当前的中间索引
不相等:
大了:往左边找
小了:往右边找
D:重新获取最小索引或者最大索引
大了:往左边找
max = mid-1;
小了:往右边找
min = mid+1;
E:回到B的位置
public static void main(String[] args) {
//定义一个数据
int[] arr = {11,22,33,44,55,66,77};
//写功能实现
int index = getIndex(arr,33);
System.out.println("index:" + index);//2
//如果传入值不存在:
int index = getIndex(arr.253);
Systme.out.pirntln("index:" + index);//-1
}
/*
* 两个明确:
* 返回值类型:int
* 参数列表:int[] arr,int value
*/
public static int getIndex(int[] arr,int value){
//定义最大索引,最小索引
int max = arr.length -1;
int min = 0;
//计算出中间索引
int mid = (max + min)/2;
//拿中间索引的值和要查找的值进行比较
while(arr[mid] != value){
if(arr[mid] > value){
max = mid-1;
}else if(arr[mid]<value){
min = mid + 1;
}
//判断如果值不存在 返回-1
if(min>max){
return -1;
}
mid = (min + max)/2;
}
return mid;
}
Arrays类:专门对数组进行的方法类
注意事项:
有一个无序数组 eg:{24,69,80,57,13}
不可先冒泡排序,再使用二分查找,应该基本查找
因为,冒泡排序后会更改数组的顺序。
Arrays:针对数组进行操作的工具类,比如说排序和查找。
1.public static String toString(int[] a) 把数组转成字符串
2.public static void sort(int[] a) 对数组进行排序
3.public static int binarySearch(int[] a,int key) 二分查找
public static void main(String[] args) {
//定义一个数组
int [] arr = {24,69,80,57,13};
//public static String toString(int[] a) 把数组转成字符串
System.out.println("排序前:" + Arrays.toString(arr));
//public static void sort(int[] a) 对数组进行排序
System.out.println(Arrays.sort(arr));
//使用二分查找需要有序数组{13, 24, 57, 69, 80} 这个数组是第二个方法排序后的结果
//public static int binarySearch(int[] a,int key) 二分查找
System.out.println(Array.binarySearch(arr,57));//2
System.out.println(Array.binarySearch(arr,577));//-6
}
最新文章
- ASP.NET Razor - C# 变量
- ubuntu 常用命令集合版(二)【大侠勿喷,菜鸟欢迎】(转)
- 【Android 系统开发】Android JNI/NDK (三) 之 JNIEnv 解析
- 【转】WMI使用的WIN32_类库名
- SQL SERVER NVARCHAR字段INSERT 中文乱码问题解决
- SDL音频播放
- 使用Enterprise Architecture绘制10种UML画画
- 使用nginx负载平衡
- (二)Windows下Redis的主从复制
- Codeforces 712B
- vue中数据双向绑定的实现原理
- JavaScript(五):函数(闭包,eval)
- JRE System Library [JavaSE-1.7](unbound)
- angularjs ng-if 中的ng-model 值作用域问题
- 【mmall】Jackson相关知识点
- [原]Jenkins(十九) jenkins再出发之jenkins邮件通知
- ubuntu配置lua环境,并进行c与lua的相互调用
- 和我一起学Effective Java之类和接口
- shell =~ 引发的思考
- python学习笔记_week4
热门文章
- GitHub标星2.6万!Python算法新手入门大全
- 配置centOS下的Python
- coding++:Spring Boot全局事务解释及使用(一)
- sql 模块 pymysql 数据库操作
- windows server 2016 远程桌面mstsc DPI(更改文本、应用和其他项目大小) 设置
- 【tensorflow2.0】处理时间序列数据
- Hadoop(十一):组合任务概述和格式
- Docker的简介以及Dockerfile编写与使用
- Java并发编程实战 01并发编程的Bug源头
- MTK Android 设置-选择日期格式 [管理和组织首选项,ListPreference,CheckBoxPreference,EditTextPreference,RingtonePreference]