---
# System prepended metadata

title: 程式設計研討專題 - project 2
tags: [程設專題]

---

# 程式設計研討專題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個數共五組，最後將時間取平均
### 計時方式
```cpp
chrono::time_point_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now())
	.time_since_epoch();
```


- `search`: $O(\lg^2n)$
![](https://i.imgur.com/WuBkRAI.png)
![](https://i.imgur.com/OZghYLn.png)

- `insert`: amortized $O(\lg n)$
![](https://i.imgur.com/KByOhpv.png)
![](https://i.imgur.com/wYCwDms.png)

- `delete`
![](https://i.imgur.com/9WArqBU.png)
![](https://i.imgur.com/uUMBLSH.png)


