# 程式設計研討專題2 - Dynamic Binary Search
###### tags: `程設專題`

109502546 資工3B 劉語芯

## 實作方法
- 用`vector<vector<Data>>` 作為資料結構，透過 `clear()` 和 `resize()` 強制處理陣列大小
- `search`
- 對於每個非空陣列由短到長進行 binary_search
- `insert`
- 用一個`tmp_array`從 $A_0$ 開始檢查，如果 $A_i$ 是空就將`tmp_array`存進 DynamicArray；如果 $A_i$ 不為空($A_i$是滿的)，則將$A_i$ merge 進`tmp_array`
- `delete`
- 每個data有一個valid表示該data是否有效
1. search target，如果target存在且valid則設為invalid，若target不在DynamicArray中或被標為invalid則回傳操作失敗
2. 檢查 target 被操作的該層(第h層)，若被標為invalid的元素數量達到該層容量的一半，則開始清理invalid data。
a. 若第h-1層是空的，將第h層中的valid data 搬至第h-1層，第h層清空
b. 若第h-1層是滿的，則將第h層中的valid data與第h-1層的所有data merge 到第h層，第h-1層清空

## pseudocode
- `search`

// -1 = not found
Search(ele): 
    for A_i <- A_0 ... A_k:
        pos <- binary_search(A_i, ele)
        if pos != -1:
            return (i, pos)
        else: continue
    return (-1,-1)

- `insert`

Insert(ele):
    if ele in DynamicArray: return false
    // search to check if ele is not in DynamicArray
    // removed this operation when time analysis
    tmp_arr <- ele
    for A_i <- A_0 ... A_k+1:
        if A_i is empty : 
            h <- i+1
            break
        tmp_arr <- merge(tmp_arr, A_i)
    A_h <- tmp_arr
    return true    

- `delete`

Delete(ele):
    (h, pos) <- Search(ele)
    if h!=-1 && pos!=-1 && ele is valid:
        set ele invalid
    if num of invalid data in A_h = 2^(h-1):
        for e in A_h:
            if e is valid:
                tmp_arr.append(e)
        A_h.clear() 
        if A_h-1 is empty :
            A_h-1 <- tmp_arr
        else:
            A_h <- merge(tmp_arr, A_h-1)

## 時間分析 - Compare with Red-Black Tree

### 實驗設計
- 利用 C++ 的 std::set 實作紅黑數的操作
- 測資
- max_query_number = 1e6
- value_range = [1, 1e9]
- 每組不重複的1e6個數共五組，最後將時間取平均
### 計時方式

chrono::time_point_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now())
	.time_since_epoch();

- `search`: $O(\lg^2n)$

- `insert`: amortized $O(\lg n)$

- `delete`