算法之查找

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
    }
}