Java 二分搜尋法(Binary Search)

摘要

參考資料：維基百科

優點：搜尋效率佳

缺點：必須事先排序、資料必需使是可直接存

Java Binary Search 內部程式碼

public boolean reverseItem(String number) {
    int low = 0;
    int high = list.size()-1;
    while(low <= high) {
        System.out.print(".");
        int mid = (low + high) / 2;
        Item midVal = list.get(mid);
        int cmp = midVal.getNumber().compareToIgnoreCase(number);

        if(cmp < 0) {
            low = mid + 1;
        } else if(cmp > 0) {
            high = mid - 1;
        } else {
            return list.get(mid).reserve();
        }
    }
    System.out.println("There is no item " + number);
    return false;
}

public boolean reserve() {
    if(!this.reserved) {
        this.reserved = true;
        return true;
    } else {
        return false;
    }
}

Java Binary Search Collections用法

public boolean reverseItem(String number) {
    Item requestItem = new Item(number);
    int foundItem = Collections.binarySearch(list, requestItem, null);
    if(foundItem >= 0) {
        return list.get(foundItem).reserve();
    } else {
        System.out.println("There is no item " + number);
        return false;
    }
}

強硬搜尋方式

public boolean reverseItem(String number) {
    Item requestedItem = null;
    for(Item item: list) {
        System.out.print(".");
        if(seat.getNumber().equals(number)) {
            requestedItem = item;
            break;
        }
    }
    if(requestedItem == null) {
        System.out.println("There is no item " + number);
        return false;
    }
    return requestedItem.reserve();
}

使用方法

if(data.reverseSeat("D12")) {
    System.out.println("Found");
} else {
    System.out.println("Not found");
}