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; // 线性探测
}
// 返回目标数据的值,如果不存在则返回-1
if (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")); // 输出:10
System.out.println(hashTable.search("xyz")); // 输出:-1
}
}