【BASE】Bin Search & Quick Sort

发布于: 2018-12-18 22:28
阅读: 33
评论: 0
喜欢: 0

问题

Bin Search with Quick Sort.

分析过程

  • 输入:一个未排序数组和一个需要查找的数
  • 输出:排序该数组,然后二分查找,返回该数的序号,不存在返回 -1
  • 思路:见注释

解决方法

// 交换指针指向的内容
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;
}

Thanks for reading.

All the best wishes for you! 💕