动态

详情 返回 返回

Java 二分法查詢 - 动态 详情

public static void main(String[] args) {
    Integer target = 7;
    // 初始化數據
    List<Integer> data = Arrays.asList(0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
    // 排序
    Collections.sort(data);
    // 輸出
    int position = test(data, target);
    System.out.println("目標數" + (position == -1 ? "不存在" : "下標為:" + position));
}

private static Integer test(List<Integer> data, Integer target) {
    if (target < data.get(0) || target > data.get(data.size() - 1)) {
        // 目標不在範圍內
        return -1;
    }
    int half;
    Integer low = 0;
    Integer high = data.size();
    while (low <= high) {
        half = (low + high) / 2;
        if (data.get(half) > target) {
            // 中間數大於目標 在左區
            high = half;
        } else if (data.get(half) < target) {
            // 中間數小於目標 在右區
            low = half;
        } else {
            return half;
        }
        if (low + 1 == high && data.get(low) != target && data.get(high) != target) {
            // 目標數不存在
            return -1;
        }
    }
    // 目標數不存在
    return -1;
}
user avatar sofastack 头像 debuginn 头像
点赞 2 用户, 点赞了这篇动态!
点赞

Add a new 评论

Some HTML is okay.