###### tags: `資料結構 & 演算法` {%hackmd @kk6333/theme-sty1 %} # DS1 - 遞迴 & 二分搜尋法 Binary Search ## 遞迴 遞迴是利用重複呼叫函數來達成目的 需要有幾項設定 - base line : 為遞迴的中止條件 - 相同函數呼叫 : 顧名思義 這邊簡單寫一個加成遞迴，在 num >= 3 時會跳出遞迴函數 ```cpp= void Add( int num ){ if(num >= 3) return; // base line Add( num + 1 ); // 重複呼叫函數 } ``` --- <br> ## 二分搜尋法 Binary Search 這邊紀錄一下第一個學到的演算法 ~ Binary Search Binary Search 的用法、寫法可以有很多種 但主要的想法是將資料"**分半**"進行操作 這邊用兩個例子來解釋、練習 <br> ### Example.1 : 尋找指定 value 的位置(index) 我們現在有一個 5 個數字按照大小排序的 List ```cpp= int arr[] = {1,3,5,8,11}; ``` 會指定一個 List 中的值，並找出其位置 index 如果使用二分搜尋法可以使用以下想法 **先上Code** ```cpp= // 二分搜尋 int BinarySearch( int arr[], int first, int last, int value ){ // 設定中點 index int mid_idx = (first + last) / 2; // 如果 List 中沒有此 value if(first == last && value != arr[mid_idx] ) return -1; // mid 為 value if ( value == arr[mid_idx]) return mid_idx; // 篩選出左邊界 else if ( value > arr[mid_idx] ) return BinarySearch( arr, mid_idx + 1, last, value ); // 篩選出右邊界 else return BinarySearch( arr, first, mid_idx - 1, value ); } ``` **解釋** :::warning > first : 左邊界 index > last : 右邊界 index 會將 List 設一個 [左邊界]、[右邊界] 當要找的 value 大於當前的中點，我們會縮減左邊界， 因為左邊的數字皆小於中點 => 小於 value，反之縮減右邊界 > ex: > value=8 > {1,3,5,8,11} => 中點=5 => 縮小左邊界 {~~1,3,5~~,8,11} 當中點等於 value 時便 return 中點 index 如無法在縮減邊界 (剩下一數字)，但未找到 value ，則傳回 -1 可以將整個方法視為不斷把資料"分半"直到剩下資料的中點為要的值 ::: --- <br> ### Example.2 : 尋找最大值 現在有一個 5 個數字不按順序排的 List ```cpp= int arr[] = {3,1,7,13,2}; ``` 要找出 List 中的最大值 **先上Code** ```cpp= // 利用二分搜尋找最大值 int MaxBinarySearch( int arr[], int first, int last){ // 只剩一個數字 (最底層) if(first == last) return first; // 中點 index int mid_idx = (first + last) / 2; // 獲得下層最大的數 index int idx1 = MaxBinarySearch( arr, mid_idx+1, last ); // 右半邊 int idx2 = MaxBinarySearch( arr, first, mid_idx ); // 左半邊 // 回傳較大的數 index if(arr[idx1] > arr[idx2]) return idx1; else return idx2; } ``` **解釋** :::warning > first : 左邊界 index > last : 右邊界 index 這邊我將 List 以"中點"將個數字劃分為了一個個的節點 當只剩一個數時 (劃分到最後一個節點) 開始回傳數字 index 並跟前一劃分的 Node 比大小，較大的數字可繼續往上比 用下圖可以更直觀解釋 ![](https://i.imgur.com/Xt329Nn.png) :::