記錄學習內容。
以下內容和截圖大多引用文章。
還不了解，內容可能有錯誤。

在一個陣列，找最大值和最小值，減少比較次數。

Maximum and minimum of an array using minimum number of comparisons
https://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

第一種方式，就是一般的想法 。

寫一個迴圈 ，跑一遍數字陣列 ， 比最小值 小 ，就更新最小值 。
比最大值 大 ，就更新 最大值 。

所以 每個數字 都要跟 最小和最大值 比較 ，比較次數 是 2n

程式裡的比較次數是 1 + 2(n-2) ， 第0項和第1項比較1次 ，其餘比較兩次

第二種方法，遞迴

寫成遞迴了 ， 很像merge sort的寫法 。
分成 兩個兩個 比較 ， 比較小的min 更新 最小值 ，比較大的 max 更新最大值

比較次數: T(n) = 3n/2 -2
不懂這個方法。
有點像:
關於 selection trees
https://www.youtube.com/watch?v=8d-rn6ZQy6U&ab_channel=%E6%B4%AA%C3%82ng%E6%98%A5%E7%94%B7Chhun-L%C3%A2m

第三種方法，迴圈

第三種寫法，比較直覺:
迴圈 不是一個一個跑 ，而是 i += 2。
先比較 兩個數字的大小 ，在跟 最大最小值在比較一次 。

陣列有幾個數字:

1 個數字 -- >比較 0次

2 個數字 -- >比較 1次

3 個數字 -- >比較 3次 ，因為假如是123 ，會23比較一次 ，2跟最小值(1)在比一次，3跟最大值(1)在比一次

4 個數字 -- >比較 4次 ，因為假如是1234 ，12先比較一次確認最小最大初始值 ，3跟4比誰大誰小一次，4跟最大值2比一次，3跟最小值1比一次 。所以 1+1+1+1 =4次

5 個數字 -- >比較 6次 ，3+3 =6

 If n is odd:    3 * (n-1)/2    (n是奇數13579)(每兩個數字比較3次，扣掉第一項)
 
 If n is even:   1 Initial comparison for initializing min and max, 
              and 3(n-2)/2 comparisons for rest of the elements  
                     =  1 + 3*(n-2)/2 = 3n/2 -2  (每兩個數字比較3次，第一項和第二項比較1次)

第一種方法的比較次數:  1 + 2(n-2)  = 2n-3

第三種方法的比較次數:  3n/2 -2

如果n是6:
第一種方法:9
第三種方法:7

如果n是20:
第一種方法:37
第三種方法:28

如果n是100:
第一種方法:197
第三種方法:148

如果n是1000:
第一種方法:1997
第三種方法:1498

比較次數差不多。一個2倍，一個1.5倍。