想用二分查找做的，不知道哪一步出错了

#include<iostream>

#include<algorithm>

using namespace std;

int serch(int a[], int n ,int num)

{

 sort(a, a + n);

 int left = 1, right = n-1;

 while (left <= right)

 {

  int mid = left + (right - left) / 2;

  if (a[mid] > a[num]) { right = mid - 1; }

  else if (a[mid] < a[num]) { left = mid + 1; }

  //找到a[i] == i,返回下标

  else return num;

 }

 return -1;

}

int main()

{

 int n;

 cin >> n;

 int* arr = new int[n+1];

 arr[0] = 0;

 for (int i = 1; i <= n; i++)

 {

  cin >> arr[i];

 }

 for (int i = 1; i <= n; i++)

 {

  if (serch(arr, n + 1, i) == arr[n]) { cout << arr[n - 1] << " " << arr[1] << endl; }

  else if (serch(arr, n + 1, i) == arr[1]) { cout << arr[n] << " " << arr[2] << endl; }

  else cout << arr[serch(arr, n + 1, i) - 1] << " " << arr[serch(arr, n + 1, i) + 1] << endl;

 }

 delete[]arr;

 return 0;

}

这。。。时间复杂度太高了吧，就算二分是对的，那也会超时的