Java中数组二分法查找
2023-09-14 08:58:14 时间
算法:当数组的数据量很大适宜采用该方法。采用二分法查找时,数据需是有序不重复的,如果是无序的也可通过选择排序、冒泡排序等数组排序方法进行排序之后,就可以使用二分法查找。 基本思想:假设数据是按升序排序的,对于给定值 x,从序列的中间位置开始比较,如果当前位置值等于 x,则查找成功;若 x 小于当前位置值,则在数列的前半段中查找;若 x 大于当前位置值则在数列的后半段中继续查找,直到找到为止,但是如果当前段的索引最大值小于当前段索引最小值,说明查找的值不存在,返回-1,不继续查找。
import java.util.Arrays;
public class 二分法 {
public static void main(String[] args) {
//1.数组基本查找功能
int[] arr = { 3, 5, 7, 9, 10 };
int index = getIndex(arr, 11);
System.out.println("index=" + index);
//2.数组二分法查找(写法1)
int[] b = { 13, 15, 19, 28, 33, 45, 78, 106 };
int index2 = halfSearch(b, 45);
System.out.println("二分法查找方法(1)index2=" + index2);
//2.数组二分法查找(写法2)
int index3 = halfSearch2(b, 99 );
System.out.println("二分法查找方法(2)index3=" + index3);
//下面是Java自带的方法,但必须保证是从小到大排序的数组
int index4 = Arrays.binarySearch(b, 33);
System.out.println("Java自带的方法执行的二分法查找 index4=" + index4);
}
/*
* 数组常见功能:查找
*/
// 两个明确:明确返回值,明确该传入那些参数
public static int getIndex(int[] arr, int key) {
for (int x = 0; x < arr.length; x++) {
if (arr[x] == key)
return x;
}
return -1;
}
/*
* 二分法查找方法法1 :必须是有序数据
*/
//第一个参数进行二分法查找的数组,第二个参数查找的值
//返回值:查找数据在数组中对应的索引值
public static int halfSearch(int[] arr, int key) {
int min,mid,max;
min = 0;
max = arr.length-1;
//数组中间值对应的索引
mid = (min+max)/2;
while(key!=arr[mid]){
if(key>arr[mid])
min = mid+1;
else if(key<arr[mid])
max = mid-1;
else if(max<min)
return -1;
//每次循环新的中间值
mid = (min+max)/2;
}
return mid;
}
/*
二分法查找方法二(原理相同,写法稍微不同)
*/
public static int halfSearch2(int[] arr, int key){
int max,min,mid;
min = 0;
max = arr.length-1;
while(min<=max){
mid = (max+min)>>1;
if(key>arr[mid])
min = mid+1;
else if(key<arr[mid])
max = mid-1;
else
return mid;
}
return -1;
}
}
相关文章
- java学习笔记2--数据类型、数组
- Java 第十一届 蓝桥杯 省模拟赛 洁净数
- Java实现 LeetCode 713 乘积小于K的子数组(子集数量+双指针)
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 554 砖墙(缝隙可以放在数组?)
- Java实现 LeetCode 525 连续数组
- Java实现 LeetCode 453 最小移动次数使数组元素相等
- Java实现 LeetCode 330 按要求补齐数组
- Java实现 蓝桥杯 图书排列(全排列)
- Java实现 LeetCode 154 寻找旋转排序数组中的最小值 II(二)
- Java实现 LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
- java实现第六届蓝桥杯生命之树
- java实现漏掉的账目明细
- Java中数组二分法查找
- java数组-顺序插入数据及二分法查找数据
- 新手学JAVA(六)----处理随机性的数据
- scala定长数组(接近Java数组)
- Java集合和数组的区别
- atitit.http get post的原理以及框架实现java php
- paip.java c# .net php python调用c++ c dll so windows api 总结
- Java如何获取IP属地 ip2region failed to create searcher with x:java.io.FileNotFoundException:( 系统找不到指定的路径)
- Java Logger(java日志)
- JAVA该队列中的数组,圆阵队列,链队列
- Java如何从数组中查找对象元素?
- 在android的jni线程C传回调函数给java