欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现常见的查找算法

程序员文章站 2024-03-20 18:06:58
...

常见的查找算法

线性查找

就是一个个遍历,查询

	private static int seqSearch(int[] array, int key) {
		for (int i = 0; i < array.length; i++) {
			if(array[i]==key) {
				return i;
			}
		}
		return -1;
	}

二分查找

每次都会去查询最中间的值是不是要查询的数,如果是就返回位置,若要查的数小于中间值,则对左边的序列再进行一次查询,若要查的数大于中间值,则对右边的序列再进行一次查询

/**
	 * 
	 * @param array 被查找的数组
	 * @param low 左索引
	 * @param high 右索引
	 * @param key 待查找的值
	 * @return key的索引
	 */
	private static int binarySearch(int[] array, int low, int high, int key) {
		Arrays.sort(array);//二分查找需要保证array数组是有序的
		if(low>high) {
			return -1;//未查到返回-1,作为索引
		}
		int mid = (low + high)/2;
		int midVal = array[mid];
		if(key<midVal) {
			return binarySearch(array,low,mid-1,key);//向左递归查询
		}else if(key>midVal) {
			return binarySearch(array,mid+1,high,key);//向右递归查询
		}else {
			return mid;//表示查到了该数
		}
	}

插值查找

插值查找对二分查找做了优化,对mid的计算方法做了改进,可以自适应地找到查找点,提高查找效率。

private static int binarySearch(int[] array, int low, int high, int key) {
		Arrays.sort(array);//插值查找需要保证array数组是有序的
		if (low > high || key < array[0] || key > array[array.length - 1]) {
			return -1;
			}
			// 求出 mid, 自适应
			int mid = low + (high - low) * (key - array[low]) / (array[high] - array[low]);
		int midVal = array[mid];
		if(key<midVal) {
			return binarySearch(array,low,mid-1,key);//向左递归查询
		}else if(key>midVal) {
			return binarySearch(array,mid+1,high,key);//向右递归查询
		}else {
			return mid;//表示查到了该数
		}
	}

分块查找

算法的思想是将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序",每个块内的的最大元素小于下一块所有元素的任意一个值

public class MyTest {
	static List<Block> blocks ;
	public static void main(String[] args) {
		buildBlocks();
		//二分法查询索引
		Scanner scan = new Scanner(System.in);
		int key = scan.nextInt();
		int tempIndex =binarySearch(key,0,blocks.size()-1);
		System.out.println("块号:"+tempIndex);
		//顺序查询Block
		int[] nums = blocks.get(tempIndex).nums;
		int i;
		for (i = 0; i < nums.length; i++) {
			if(nums[i] == key) {
				System.out.println("索引为:"+i);
				break;
			}
		}
		if(i >= nums.length) {
			System.out.println("未查询到\n");
		}
		
	}
    
    
    //二分法查找索引表
	private static int binarySearch(int key,int low,int high) {
		int mid = (low + high)/2;
		if(low >= high) {
			return mid;
		}else {
			if(blocks.get(mid).maxKey==key) {
				return mid;
			}else if(blocks.get(mid).maxKey<key) {
				return binarySearch(key,mid+1,high);
			}else  {
				return binarySearch(key,0,mid);
			}
		}
		
	}
    
    //用来初始化数据,也可自己输入,自己输入还可以省了循环找到最大值
	private static void buildBlocks() {
		blocks = new ArrayList<>();
		blocks.add(new Block(new int[] {4,7,9,8}));
		blocks.add(new Block(new int[] {10,15,11,14}));
		blocks.add(new Block(new int[] {24,25,42,16}));

	}
}

//块,里面包含一段未排序过的数字序列
class Block{
	int []nums;
	int length;
	int maxKey;
	int maxKeyPos;
	public Block( int[] nums) {
		this.nums = nums;
		this.length = nums.length;
		
		maxKey = nums[0];
		for (int i = 0; i < nums.length; i++) {
			if(maxKey < nums[i]) {
				maxKey =  nums[i] ;
				maxKeyPos = i;
			}
			
		}
	}
}

相关标签: 算法 java

上一篇: 折半查找

下一篇: