给定如下C++程序，假设数组的值域范围是D，求该程序的时间复杂度：

#include <iostream>
#include <algorithm>

bool check(int n, int a[], int k, int dist) {
 int cnt = 1;
 int last = a[0];

 for (int i = 1; i < n; i++) {
  if (a[i] - last >= dist) {
   cnt++;
   last = a[i];
  }
 }

 return cnt >= k;
}

int solve(int n, int a[], int k) {
 std::sort(a, a + n);

 int l = 0;
 int r = a[n - 1] - a[0];

 while (l < r) {
  int mid = (l + r + 1) / 2;

  if (check(n, a, k, mid))
   l = mid;
  else
   r = mid - 1;
 }

 return l;
}

int main() {
 int a[] = {1, 2, 8, 4, 9};
 int n = 5;
 int k = 3;

 std::cout << solve(n, a, k) << std::endl;

 return 0;
}