目录
1、基本查找方法
基本查找核心：从0索引开始挨个往后查找
需求：定义一个方法，利用基本查找，查询某个元素是否存在
代码如下
/**
* @authorDesc
* @author
* @date
* @version 1.0.0
* @description 基本查找
* 核心：从0索引开始挨个往后查找
* 需求：定义一个方法，利用基本查找，查询某个元素是否存在
*/
public class BasicSearch {
public static void main(String[] args) {
int[] numArray = {1,2,3,4,5,6,4,4};
int number = 4;
System.out.println(search(numArray,number));
}
/**
* @description
* @author
* @date
* @param numArray 数组
* @param number 要查找的数字
* @retur {@link int} 返回元素下表
*/
public static int search(int[]numArray,int number){
for (int i = 0; i < numArray.length; i++) {
if (numArray[i] == number){
return i;
}
}
return -1;
}需求：定义一个方法，利用基本查找，查询某个元素是否存在，如果有重复的元素，把所有元素找出
/**
* @description
* @author
* @date
* @param numArray 数组
* @param number 要查找的数字
* @return {@link List} 返回元素下标集合
*/
public static List search(int[]numArray,int number){
List<Integer> listnum = new ArrayList<>();
for (int i = 0; i < numArray.length; i++) {
if (numArray[i] == number){
listnum.add(i);
}
}
return listnum;
}
}2、二分查找
前提条件：数组中的数据必须是有序的
核心：每次排除一半的查找范围
代码如下
/**
* @authorDesc
* @author
* @date
* @version 1.0.0
* @description 二分查找
* 核心：每次排除一半的查找范围
* 需求：定义一个方法利用二分查找，查询某个元素是否在数组中
*/
public class BinarySearch {
public static void main(String[] args) {
int [] numArray = {1,2,3,4,5,6};
int number = 3;
System.out.println(search(numArray,number));
}
/**
* @description
* @author
* @date
* @param numArray 数组
* @param number 查找的数字
* @return {@link int} 返回在数组中的下标
*/
public static int search(int [] numArray, int number){
//定义两个变量记录要查找的范围 min数组第一个元素的索引，max 数组最后一个元素的索引
int min = 0;
int max = numArray.length - 1;
//利用循环查找
while (true){
if (min > max){
return -1;
}
//找到min和max的中间值
int mid = (min + max) / 2;
// 用mid 指向的元素和要查找的元素进行比较
if (numArray[mid] > number){
//要查找的数字在mid的左边
//min不变， max = mid - 1
max = mid - 1;
}else if (numArray[mid] < number){
//要查找的数字在mid的右边
//max不变，min = mid + 1
min = mid + 1;
}else {
//查找的元素和mid指向得到元素一样
return mid;
}
}
}
}
二分查找的优势：提高查找效率
二份查找条件：1、数据必须是有序的
2、如果数据是乱的，先排序再用二分法查找得到的索引没有意义，只能确定当前数字在数组中是否存在，因为排序后的数字位置发生了变化
二分查找的过程：min和max表示当前要查找的范围
mid是在min和max中间的数字
如果要查找的元素在mid左边，缩小范围时，min不变，max等于mid减1
如果要查找的元素在mid右边，缩小范围时，max不变，min等于mid减1
3、插值查找
//插值查找
int mid = min + (number - numArray[min]) /(numArray[max] - numArray[min]) * (max - min);和二分查找相似，将中间值mid改为：
int mid = min + (number – numArray[min]) /(numArray[max] – numArray[min]) * (max – min);
4、分块查找
原则：1、前一块中的最大数据，小于后一块中的所有数据（块内无序，块间有序）
2、块数数量一般等于元素个数的开根号，比如16个数字一般分为4块
核心：先确定要查找的元素在哪一块，然后在挨个查找
代码如下
/**
* @authorDesc
* @author
* @date
* @version 1.0.0
* @description 使用分块查找数组中的元素
*/
public class BlockSearch {
public static void main(String[] args) {
int[] numArray = {2,3,1,4,
8,6,7,5,
9,11,10,12,
15,14,13,16};
//创建三个快的对象
Block b1 = new Block(4,0,3);
Block b2 = new Block(8,4,7);
Block b3 = new Block(12,8,11);
Block b4 = new Block(16,12,15);
//定义数组用来管理三个快的对象
Block [] blockArray = {b1,b2,b3,b4};
//定义一个变量用来记录要找的元素
int number = 5;
//调用方法，传递索引表，数组，要查找的元素
int index = getIndex(blockArray,numArray,number);
System.out.println(index);
}
/**
* @description 定义一个方法，用来确定number在哪一块中
* @author
* @date
* @param blockArray 数组
* @param number 要查找的元素
* @return {@link int} 返回下标
*/
public static int findBlock(Block[] blockArray,int number){
//Block b1 = new Block(4,0,3);-----0
//Block b2 = new Block(8,4,7);-----1
//Block b3 = new Block(12,8,11);----2
//Block b4 = new Block(16,12,15);----3
//从0索引开始遍历，如果bunber小于max，那么number就在这一块中
for (int i = 0; i < blockArray.length; i++) {
if (number <= blockArray[i].getMax()){
return i;
}
}
return -1;
}
/**
* @description
* @author
* @date
* @param blocks 传递索引表，，
* @param numArray 数组
* @param number 要查找的元素
* @return {@link int} 返回下标
*/
public static int getIndex(Block [] blocks,int [] numArray,int number){
//确定number实在那一块中
int indexBlock = findBlock(blocks,number);
if (indexBlock == -1){
return -1;
}
//获取这一块的起始索引和结束索引
//Block b1 = new Block(4,0,3);-----0
//Block b2 = new Block(8,4,7);-----1
//Block b3 = new Block(12,8,11);----2
//Block b4 = new Block(16,12,15);----3
int startIndex = blocks[indexBlock].getStartIndex();
int endIndex = blocks[indexBlock].getEndIndex();
//循环遍历
for (int i = startIndex; i < endIndex; i++) {
if (numArray [i] == number){
return i;
}
}
return -1;
}
static class Block{
private int max;//最大值
private int startIndex;//起始索引
private int endIndex;//结束索引
public Block() {
}
public Block(int max, int startIndex, int endIndex) {
this.max = max;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
/**
* 获取
* @return max
*/
public int getMax() {
return max;
}
/**
* 设置
* @param max
*/
public void setMax(int max) {
this.max = max;
}
/**
* 获取
* @return startIndex
*/
public int getStartIndex() {
return startIndex;
}
/**
* 设置
* @param startIndex
*/
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
/**
* 获取
* @return endIndex
*/
public int getEndIndex() {
return endIndex;
}
/**
* 设置
* @param endIndex
*/
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/93361.html
