算法之查找

1、顺序查找：

package com.arithmetic.search;
//顺序查找
//sequentialSearch 方法接收一个整数数组和一个目标元素作为参数，并使用顺序查找的方式在数组中查找目标元素。
//它通过循环遍历数组元素，逐个与目标元素比较，如果找到了目标元素，则返回其索引位置。
//如果遍历完整个数组仍然没有找到目标元素，则返回 -1。
//在 main 方法中，创建一个测试数组并定义一个目标元素，然后调用 sequentialSearch 方法进行查找。
//根据返回的结果判断是否找到了目标元素，并输出相应的提示信息。
//顺序查找的时间复杂度是 O(n)，其中 n 是数组的长度。
//它是一种简单直接的查找算法，适用于小规模的数组或不需要频繁查找的情况。但对于大规模的数组，效率较低。
//如果需要在大规模数组中进行频繁查找，可以考虑其他更高效的查找算法，如二分查找或哈希查找。
public class SequentialSearchDemo {public static void main(String[] args) {int[] arr = {5, 2, 9, 1, 3, 6, 4, 8, 7};int target = 3;int index = sequentialSearch(arr, target);if (index != -1) {System.out.println("目标元素 " + target + " 在数组中的索引位置为 " + index);} else {System.out.println("目标元素 " + target + " 不在数组中");}}public static int sequentialSearch(int[] arr, int target) {for (int i = 0; i < arr.length; i++) {if (arr[i] == target) {return i; // 找到了目标元素，返回索引位置}}return -1; // 没有找到目标元素，返回 -1}
}

2、二分查找：

package com.arithmetic.search;
//二分查找
//binarySearch 方法接收一个有序整数数组和一个目标元素作为参数，并使用二分查找的方式在数组中查找目标元素。
//它维护两个变量 left 和 right，分别指向查找范围的左边界和右边界。
//通过循环不断缩小查找范围，每次将查找范围的中间元素与目标元素进行比较。
//如果中间元素等于目标元素，则返回它的索引位置。
//如果中间元素小于目标元素，则目标元素在右半部分，缩小范围到右半部分；如果中间元素大于目标元素，则目标元素在左半部分，缩小范围到左半部分。
//循环直到找到目标元素或查找范围缩小为 0。
//在 main 方法中，创建一个有序数组并定义一个目标元素，然后调用 binarySearch 方法进行查找。
//根据返回的结果判断是否找到了目标元素，并输出相应的提示信息。
//二分查找的时间复杂度是 O(log n)，其中 n 是数组的长度。
//相比于顺序查找，二分查找的效率更高，但要求数组必须是有序的。
//如果数组无序，需要先进行排序操作，再进行二分查找。
public class BinarySearchDemo {public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};int target = 6;int index = binarySearch(arr, target);if (index != -1) {System.out.println("目标元素 " + target + " 在数组中的索引位置为 " + index);} else {System.out.println("目标元素 " + target + " 不在数组中");}}public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到了目标元素，返回索引位置} else if (arr[mid] < target) {left = mid + 1; // 目标元素在右半部分，缩小范围到右半部分} else {right = mid - 1; // 目标元素在左半部分，缩小范围到左半部分}}return -1; // 没有找到目标元素，返回 -1}
}

3、散列查找：

package com.arithmetic.search;
//散列查找
//一个简单的哈希表，使用了开放地址法的线性探测解决冲突。
//通过insert方法插入数据，并通过search方法查找数据。
//可以根据自己的需求修改散列函数和解决冲突的方法。
public class HashTableDemo {private static final int TABLE_SIZE = 10; // 哈希表的大小private Entry[] table; // 哈希表的数组public HashTableDemo() {table = new Entry[TABLE_SIZE]; // 初始化哈希表}// 插入数据public void insert(String key, int value) {int hash = getHash(key); // 计算散列值int index = hash % TABLE_SIZE; // 计算索引位置// 如果索引位置已经被占用，则处理冲突if (table[index] != null) {// 处理冲突的方法可以有很多种，这里使用开放地址法的线性探测while (table[index] != null) {index = (index + 1) % TABLE_SIZE; // 线性探测}}table[index] = new Entry(key, value); // 插入数据}// 查找数据public int search(String key) {int hash = getHash(key); // 计算散列值int index = hash % TABLE_SIZE; // 计算索引位置// 如果索引位置不是目标数据，则继续线性探测while (table[index] != null && !table[index].getKey().equals(key)) {index = (index + 1) % TABLE_SIZE; // 线性探测}// 返回目标数据的值，如果不存在则返回-1if (table[index] != null) {return table[index].getValue();} else {return -1;}}// 计算散列值的方法，这里简单地将每个字符的ASCII码相加private int getHash(String key) {int hash = 0;for (int i = 0; i < key.length(); i++) {hash += key.charAt(i);}return hash;}// 定义存储数据的Entry类private static class Entry {private String key;private int value;public Entry(String key, int value) {this.key = key;this.value = value;}public String getKey() {return key;}public int getValue() {return value;}}public static void main(String[] args) {HashTableDemo hashTable = new HashTableDemo();// 插入数据hashTable.insert("abc", 10);hashTable.insert("def", 20);hashTable.insert("ghi", 30);// 查找数据System.out.println(hashTable.search("abc")); // 输出：10System.out.println(hashTable.search("xyz")); // 输出：-1}
}