# 问题 Bin Search with Quick Sort. # 分析过程 - 输入：一个未排序数组和一个需要查找的数 - 输出：排序该数组，然后二分查找，返回该数的序号，不存在返回 -1 - 思路：见注释 # 解决方法 ```c // 交换指针指向的内容 void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } // 快速排序 void quickSort(int *arr, int first, int last) { if (first >= last) { return; } int low = first, high = last; // 取第一个为阈值 int key = arr[low]; while (low < high) { // 从最右边开始往左扫描，扫到比阈值小的，交换该值和阈值 while (low < high && key <= arr[high]) { --high; } // 此时阈值的下标为 high if (key > arr[high]) { swap(arr + low, arr + high); ++low; } // 从左边开始往右边扫描，扫到比阈值大的，交换该值和阈值 while (low < high && key >= arr[low]) { ++low; } // 此时阈值的下标为 low if (key < arr[low]) { swap(arr + low, arr + high); --high; } // 一次扫描结束以后，阈值被交换了两次，此时阈值又回到了第 low 个 } // 全部扫描结束以后，比阈值小的已经都到左边，比阈值大的已经都到了右边 // 此时 low 和 high 相等，就是当前阈值所处的位置 quickSort(arr, first, low - 1); quickSort(arr, low + 1, last); } int binSearch(int num, int *arr, int first, int last) { if (first > last) { return -1; } // 取中间下标，避免使用 (last + first) / 2 防止溢出 int mid = first + (last - first) / 2; if (num == arr[mid]) { return mid; } else if (num < arr[mid]) { return binSearch(num, arr, first, mid - 1); } else { return binSearch(num, arr, mid + 1, last); } } int main() { int arr[] = {35, 12, 37, -58, 54, 76, 22}; int count = sizeof(arr) / sizeof(int); quickSort(arr, 0, count - 1); for (int i = 0; i < count; i++) { printf("%d, ", arr[i]); } printf("\n"); int num = binSearch(54, arr, 0, count - 1); printf("%d\n", num); return 0; } ```