第八章：查找

1.概念

查找：

查找方式：

2.顺序表查找

2.1.概念

顺序查找（被查找的序列可以无序）

线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。

由于顺序查找是从头插到尾，所以这种方法的查询时间慢。

2.1.顺序表查找算法

优化——引入哨兵

2.3.举例

图例说明：原始数据：int[] a={4,6,2,8,1,9,0,3}; 要查找数字：8

找到数组中存在数据8，返回位置。

代码演示：

import java.util.Scanner;
/*

 * 顺序查找

 */
public class SequelSearch {
  public static void main(String[] arg) {  
    int[] a={4,6,2,8,1,9,0,3};
    Scanner input=new Scanner(System.in);
    System.out.println("请输入你要查找的数：");
    //存放控制台输入的语句
　　int num=input.nextInt();
　　//调用searc()方法，将返回值保存在result中
    int result=search(a, num);
    if(result==-1){
    　　 System.out.println("你输入的数不存在与数组中。");
    }
    else
   　　  System.out.println("你输入的数字存在，在数组中的位置是第："+(result+1)+"个");
}

  //顺序排序算法
  public static int search(int[] a, int num) {        
    for(int i = 0; i < a.length; i++) {
        if(a[i] == num){//如果数据存在
            return i;//返回数据所在的下标，也就是位置
        }
    } 
    return -1;//不存在的话返回-1
 }
}

运行截图：

3.有序表查找

3.1.折半查找

代码演示

代码实现

我以{1,2,3,4,5,6,6,6}这个数组作为被查询序列，下面代码使用情景为序列从小到大排序。

public static List<Integer> binarySearch(int arr[], int left, int right, int findVal) {
		int mid = (left + right) / 2;
		int midVal = arr[mid];

		if (left > right) {//left > right代表序列没有要找的元素
			return new ArrayList<Integer>();
		}

		if (findVal > midVal) {// 查找元素大于中间值，向右递归
			return binarySearch2(arr, mid + 1, right, findVal);
		}

		if (findVal < midVal) {//查找元素小于中间值，向左递归
			return binarySearch2(arr, left, mid - 1, findVal);
		}

		else {//找到被查找元素
			List<Integer> list = new ArrayList<Integer>();
			int temp = mid - 1;//从查找元素的左边遍历查找是否还有相同元素

			while (true) {
				if (temp < 0 || arr[temp] != findVal) {//退出左边遍历查找条件
					break;
				}
				list.add(temp);
				temp -= 1;
			}
			list.add(mid);

			temp = mid + 1;//从查找元素的右边遍历查找是否还有相同元素

			while (true) {
				if (temp > right || arr[temp] != findVal) {//退出右边遍历查找条件
					break;
				}
				list.add(temp);
				temp += 1;
			}
			return list;
		}
}

3.2.插值查找

其实就是插入法

概念：

原理：

代码实现：

public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 6, 6, 6 };
		List<Integer> list = insertValueSearch(arr, 0, arr.length - 1, 6);
		System.out.println("index = " + list);

}

public static List<Integer> insertValueSearch(int arr[], int left, int right, int findVal) {
		int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
		int midVal = arr[mid];

		if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
			return new ArrayList<Integer>();
		}

		if (findVal > midVal) {
			return insertValueSearch(arr, mid + 1, right, findVal);
		}
		if (findVal < midVal) {
			return insertValueSearch(arr, left, mid - 1, findVal);
		} else {
			List<Integer> list = new ArrayList<Integer>();
			int temp = mid - 1;
			while (true) {
				if (temp < 0 || arr[temp] != findVal) {
					break;
				}
				list.add(temp);
				temp -= 1;
			}
			list.add(mid);

			temp = mid + 1;
			while (true) {
				if (temp > right || arr[temp] != findVal) {
					break;
				}
				list.add(temp);
				temp += 1;
			}
			return list;
		}
}

4.线性表索引

4.1.概念

4.2.稠密索引

4.3.倒排索引

参考资料：https://blog.csdn.net/weixin_44824500/article/details/104760260