Java 線性與二分查找算法實現詳解

線性查找

線性查找是最基本的查找算法：從數組首元素開始逐個比較，直到找到目標值或遍歷完畢。時間複雜度為 O(n)。

二分查找

二分查找要求數組已排序。每次比較中間元素，根據大小關係將查找範圍縮小一半。時間複雜度為 O(log n)。

完整代碼實現

package com.zc.manythread;

import java.util.Random;
import java.util.Scanner;

public class LinearSearch {

    // 線性查找
    public static int linearSearch(int[] list, int item) {
        for (int i = 0; i < list.length; i++) {
            if (list[i] == item) {
                return i; // 返回位置
            }
        }
        return -1; // 未找到
    }

    // 二分查找，數組需預先排序（升序）
    public static int binarySearch(int[] list, int item) {
        int left = 0;
        int right = list.length - 1; // 修正：right 應為 length-1
        while (left <= right) {
            int mid = (left + right) / 2;
            if (list[mid] == item) {
                return mid;
            } else if (list[mid] > item) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    // 生成不重複隨機數組
    private static int[] createData(int count) {
        int[] data = new int[count];
        Random rand = new Random();
        boolean[] used = new boolean[100];
        for (int i = 0; i < count; i++) {
            int num;
            do {
                num = rand.nextInt(100);
            } while (used[num]);
            used[num] = true;
            data[i] = num;
        }
        return data;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 線性查找示例
        int[] list = createData(10);
        System.out.println("原始數列:");
        for (int v : list) System.out.print(v + " ");
        System.out.println("\n請輸入要查詢的數:");
        int key = in.nextInt();
        int pos = linearSearch(list, key);
        if (pos >= 0) System.out.println("找到，位置: " + (pos + 1));
        else System.out.println("未找到");

        // 二分查找示例
        int[] sorted = {2, 4, 6, 8, 10, 12, 13, 14, 15, 16};
        System.out.println("有序數據:");
        for (int v : sorted) System.out.print(v + " ");
        System.out.println("\n請輸入要查詢的數:");
        int key2 = in.nextInt();
        int pos2 = binarySearch(sorted, key2);
        if (pos2 >= 0) System.out.println("找到，位置: " + (pos2 + 1));
        else System.out.println("未找到");
    }
}

關鍵點說明

• 二分查找前提：數組必須有序。本示例中 linearSearch 用於無序數組，binarySearch 用於有序數組。
• 邊界處理：代碼中將 right 初始化為 list.length - 1，避免越界。
• 隨機數組生成：使用布爾標記數組確保生成的隨機數不重複。

總結

線性查找適用於小規模或無序數據；二分查找在有序大數據集中極其高效。掌握兩者的適用場景與實現細節，是算法基礎的重要一環。