（請先看置頂博文）本博打開方式，請詳讀_liO_Oil的博客-CSDN博客_怎么把androidstudio卸載干凈

一、題目大意

查找最接近的元素（分治法/二分查找）：在一個非降序列中，查找與給定值最接近的元素。

[輸入]

第一行包含一個整數n，為非降序列長度。

第二行包含n個整數，為非降序列各元素。

第三行包含一個整數m，為要詢問的給定值個數。1 <= m <= 10000。

接下來m行，每行一個整數，為要詢問最接近元素的給定值。所有給定值的大小均在0-1,000,000,000之間

[輸出]

m行，每行一個整數，為最接近相應給定值的元素值，保持輸入順序。若有多個值滿足條件，輸出最小的一個

input：

3

2 5 8

2

10

5

output：

8

5

二、主要思想

? ? ? ?我認為這道題考察的知識點有兩個：一個是遞歸，另一個是二分查找。這個二分查找和通常的二分查找不一樣，題目要求查找最接近的，所以這就給題目求解帶來了很大的難度。我在寫程序時，先在紙上模擬，用到了很多的if和else判斷語句，對可能出現的各種情況進行細分，最后實現了一個finder（）函數，用于在遞增數列中查找與要查找的數字最近的數字。

? ? ? ?關于二分

在寫代碼的時候遇到一個問題，就是關于long long的使用問題：

1、long long定義時，如果還用scanf()函數輸入，編譯器不報錯，但是輸入的數字完全改變。

針對這個問題，我也找到了相應的解決辦法，請看這篇文章：C語言（CED）與long long相關的知識_liO_Oil的博客-CSDN博客

三、具體實現

#include<stdio.h>
#include<stdlib.h>
int a[1000];//存放升序排列的一列數字
int b[1000];//存放要找的數字
int m;//輸入要查找的數的個數
long long finder(int mx, int mn, int mid, int j)//
{//第一步區分查找的這個數是否在開區間內if (b[j] <= a[mn] || b[j] >= a[mx])//不在{//對內部進行細分，到底是比最小的還小，還是比最大的還大if (b[j] <= a[mn])  //比最小的還小printf("%d\n", a[mn]);else//比最大的還大printf("%d\n", a[mx]);}else//位于最小的數字和最大的數字之間{//根據mid來分，比mid大還是比mid小，還是和mid相等if (a[mn]<b[j] && b[j]<a[mid])//比mid小{if (mid - mn != 1){mx = mid - 1;//將mx替換為midmid = (mn + mx) / 2;//重新計算mid下標finder(mx, mn, mid, j);}else{if (a[mid] - b[j]>b[j] - a[mn])//比較距離printf("%d\n", a[mn]);else if (a[mid] - b[j]<b[j] - a[mn])printf("%d\n", a[mid]);elseprintf("%d %d\n", a[mn], a[mid]);}}else if (a[mid]<b[j] && b[j]<a[mx])//比mid大{if (mx - mid != 1){mn = mid;//重新計算mnmid = (mn + mx) / 2;//重新計算mid下標finder(mx, mn, mid, j);}else{if (b[j] - a[mid]>a[mx] - b[j])printf("%d\n", a[mx]);else if (b[j] - a[mid]<a[mx] - b[j])printf("%d\n", a[mid]);elseprintf("%d %d\n", a[mid], a[mx]);}}else//和mid相等printf("%d\n", b[j]);}return 0;
}
int main()
{int j = 0;//用作函數循環的int n;//輸入非降序序列的長度scanf("%d", &n);for (int i = 0; i<n; i++) //循環輸入n個數字scanf("%d", &a[i]);scanf("%d", &m);    //輸入要查詢的數字個數for (int i = 0; i<m; i++) //循環輸入要查找的數，存在b[i]中scanf("%d", &b[i]);int mx = n - 1, mn = 0;int mid = (mx + mn) / 2;for (j = 0; j<m; j++)//循環調用函數，把b[j]中存儲的所有要找的數字找完finder(mx, mn, mid, j);system("pause");return 0;}

在寫完這個程序后，我用大量的數據，科學的測試方法（邊緣測試）進行測試，結果是沒有發現問題，如果大家在測試過程中發現問題，請及時留言，歡迎！