折半查找与哈希查找

折半查找，二分查找，本质上是一种方法的两种叫法，都是对一个有序数组进行查找排序的方法

折半查找不能确定数据在原数组中的位置，只能确定数据在原数组中，查找到数据在排序后的位置

哈希查找，使用Map统计设计数据在原数组中的位置

图记录的数据是，数据的内容作为Key，数据的位置作为Value

public class ChickNum {
    // 使用折半查找查找排序后的某个元素
    // 折半查找，二分查找，本质上是一种方法的两种叫法，都是对一个有序数组进行查找排序的方法
    // 折半查找不能确定数据在原数组中的位置，只能确定数据在原数组中，查找到数据在排序后的位置
    private static int chickNum(int[] nums, int target){
        System.out.println("数组未排序，排序前的序列为：");
        System.out.println(Arrays.toString(nums));

        sort(nums);

        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target){
                return mid;
            }else {
                if (target < nums[mid]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
        }

        return -1;
    }

    // 使用map查找原数组位置
    private static int chickNumForMap(int[] nums, int target){
        Map<Integer, Integer> map = toMap(nums);
        if (map.containsKey(target)){
            return map.get(target);
        }
        return -1;
    }

    // 查找数据在原数组中的位置
    // 图记录的数据是，数据的内容作为Key，数据的位置作为Value
    private static Map<Integer, Integer> toMap(int[] nums){
        System.out.println("数组未排序，排序前的序列为：");
        System.out.println(Arrays.toString(nums));

        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        System.out.println("原数据，图已完成记录：");
        System.out.println(map);
        return map;
    }

    private static void sort(int[] nums){
        Arrays.sort(nums);
        System.out.println("数组已排序，排序后的序列为：");
        System.out.println(Arrays.toString(nums));
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 2, 3, 4, 6, 666, 8, 9, 10};
        int target = 5;
        System.out.println("数据已找到，排序后的位置为：" + chickNum(nums, target));
        System.out.println();

        nums = new int[]{1, 5, 2, 3, 4, 6, 666, 8, 9, 10};
        System.out.println("数据已找到，原数据的位置为：" + chickNumForMap(nums, target));
    }
}

执行结果

数组未排序，排序前的序列为：
[1, 5, 2, 3, 4, 6, 666, 8, 9, 10]
数组已排序，排序后的序列为：
[1, 2, 3, 4, 5, 6, 8, 9, 10, 666]
数据已找到，排序后的位置为：4

数组未排序，排序前的序列为：
[1, 5, 2, 3, 4, 6, 666, 8, 9, 10]
原数据，图已完成记录：
{1=0, 2=2, 3=3, 4=4, 5=1, 6=5, 8=7, 9=8, 666=6, 10=9}
数据已找到，原数据的位置为：1