申論題

三、給定一個正整數 n，找出關鍵整數（Pivot integer）x 使得：所有介於 1 至 x 之區間（含 1 與 x）的元素總和，等於所有介於 x 至 n 之區間（含 x 與 n）的元素總和，回傳關鍵整數 x。若不存在此類關鍵整數，則回傳-1。 例如當 n=8 時，因為 1+2+3+4+5+6=6+7+8，所以回傳關鍵整數 x=6，而當 n=1 時，因為 1=1，所以回傳關鍵整數 x=1，但當 n=4 時，因為不存 在此類關鍵整數，所以回傳-1。若使用線性搜尋法（Linear search），進行關鍵整數的尋找，當 n 的值較大時，計算效率很低，並不是一個理想的解題方式，必須使用其他較有計算效率的搜尋方法，例如二元搜尋法 （Binary search）。請使用 Java 或 C++實作一完整程式，其中輸入資料的第一行包含一個正整數 n，1 ≤ n ≤ 1000，代表區間上限，在讀入 n 後，透過二元搜尋法找尋一個區間[1,n]中的關鍵整數，若存在，則回傳關鍵整數值，否則，回傳-1。 （20 分）