线性表查找

线性表的查找可以采用顺序查找和二分查找来完成，在进行查找操作时，与数据存储结构关系不大，即不论采用的是顺序表还是链表，查找的基本思路都是一致的。

顺序查找

逐个比较查询，如果找到，返回数据或索引，如果最后也没找到，返回null或-1，在各个节点查找概率相同的情况下，默认查询长度为一半长度，所以时间复杂度：T(n) = O(n)
【在成绩中查询分数为100的第一个分数】

package com.search;/*** 在分数数组中查询指定分数的索引* 时间复杂度：T(n)=O(n)* 空间复杂度：S(n)=O(1)*/
public class TestSearchOrder {public static void main(String[] args) {//给定分数数组int[] scores = new int[]{66,72,54,88,100,96,99,100,75};//给定要查找的分数int score = 100;//完成查找int index = search(100,scores);//输出结果if(index==-1){System.out.println("分数不存在！");}else{System.out.println("第一个"+score+"分的索引："+index);}}public static int search(int value,int[] values){for(int x=0;x<values.length;x++){if(values[x]==value){return x;}}return -1;}
}

二分查找

二分查找又称折半查找，这种查找方法需要待查找的线性表满足以下两个条件：

1. 查找表必须使用顺序结构存储
2. 查找表必须按关键字大小有序排序

【33的查找过程】

【79的查找过程】

【代码实现二分查找】

package com.search;/*** 前提：顺序结构、按关键字排列*/
public class BinarySearchTest {public static void main(String[] args) {//给定数组int[] array = new int[]{0,1,2,3,4,5,6,7,8,9,10};//二分查找System.out.println(binarySearch(9,array));//二分查找递归实现System.out.println(binarySearchRecursive(10,array));}/*** 二分查找 不使用递归* 时间复杂度：T(n)=O(log2n)* 空间复杂度：S(n) = O(1)* @param key 要查找的值* @param array 在数组array中查找* @return 若找到，返回key的索引，否则返回-1*/public static int binarySearch(int key,int[] array){if(array!=null){//指定low和highint low = 0;int high = array.length-1;while(high>=low){int mid = (low+high)/2;if(array[mid]==key){return mid;}else if(array[mid]<key){low = mid+1;}else if(array[mid]>key){high = mid-1;}}}return -1;}/*** 二分查找递归操作* 时间复杂度：T(n)=O(log2n)* 空间复杂度：S(n) = O(log2n)*/public static int binarySearchRecursive(int key,int[] array){//指定low和highint low = 0;int high = array.length-1;return binarySearchRecursiveTools(key,array,low,high);}public static int binarySearchRecursiveTools(int key,int[] array,int low,int high){if(low>high){//递归结束条件return -1;}int mid = (low+high)/2;if(array[mid]==key){//数据找到了，递归结束return mid;}else if(array[mid]>=key){return binarySearchRecursiveTools(key,array,low,mid-1);}else if(array[mid]<key){return binarySearchRecursiveTools(key,array,mid+1,high);}return -1;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！