怎样用指针实现数组的快速查找二分查找的指针优化版本-C++-PHP中文网

使用指针实现二分查找的核心目的是为了更直观地操作内存地址，深入理解底层机制。1. 指针允许直接操作内存地址，有助于理解内存布局和访问方式；2. 更符合c++/c++语言特性，数组名本质上是指针；3. 通过指针算术可减少因下标计算错误导致的bug；4. 性能上与索引版本差异不大，现代编译器优化后两者效率接近；5. 使用时需注意避免空指针、指针越界、类型不匹配等陷阱；6. 最佳实践包括边界检查、明确指针语义、测试极端情况及保持代码可读性。

怎样用指针实现数组的快速查找二分查找的指针优化版本

用指针来实现数组的快速查找，本质上就是利用二分查找的逻辑，但将操作对象从数组下标直接转向内存地址。这听起来可能有点“炫技”，但确实能让你更直接地感受数据在内存中是如何被访问和处理的，尤其是在C/C++这类语言里，它提供了一种更贴近硬件的视角。

#include <stddef.h> // For NULL

// 假设我们有一个已排序的整数数组
// target是要查找的值
// arr是数组的起始地址
// size是数组的元素个数
int* find_with_pointer_binary_search(int* arr, size_t size, int target) {
    if (arr == NULL || size == 0) {
        return NULL; // 空数组或无效指针，直接返回
    }

    int* low = arr;
    int* high = arr + size - 1; // 指向最后一个元素的地址

    while (low <= high) {
        // 计算中间元素的地址。这里需要注意，直接 (low + high) / 2 是错误的，
        // 因为指针不能直接相加再除。我们计算的是偏移量。
        // (high - low) 得到的是两个指针之间的元素个数（或字节数，取决于指针类型）。
        // 除以2后，再加到low上，得到中间元素的地址。
        int* mid = low + (high - low) / 2;

        if (*mid == target) {
            return mid; // 找到了，返回该元素的地址
        } else if (*mid < target) {
            low = mid + 1; // 目标值在右半部分，将low移到mid的下一个位置
        } else { // *mid > target
            high = mid - 1; // 目标值在左半部分，将high移到mid的前一个位置
        }
    }

    return NULL; // 没有找到
}

/*
// 示例用法
#include <stdio.h>

int main() {
    int sorted_array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    size_t array_size = sizeof(sorted_array) / sizeof(sorted_array[0]);

    int target1 = 50;
    int* result1 = find_with_pointer_binary_search(sorted_array, array_size, target1);
    if (result1 != NULL) {
        printf("Found %d at address %p, value: %d\n", target1, (void*)result1, *result1);
    } else {
        printf("%d not found.\n", target1);
    }

    int target2 = 35;
    int* result2 = find_with_pointer_binary_search(sorted_array, array_size, target2);
    if (result2 != NULL) {
        printf("Found %d at address %p, value: %d\n", target2, (void*)result2, *result2);
    } else {
        printf("%d not found.\n", target2);
    }

    int target3 = 100;
    int* result3 = find_with_pointer_binary_search(sorted_array, array_size, target3);
    if (result3 != NULL) {
        printf("Found %d at address %p, value: %d\n", target3, (void*)result3, *result3);
    } else {
        printf("%d not found.\n", target3);
    }

    int target4 = 10;
    int* result4 = find_with_pointer_binary_search(sorted_array, array_size, target4);
    if (result4 != NULL) {
        printf("Found %d at address %p, value: %d\n", target4, (void*)result4, *result4);
    } else {
        printf("%d not found.\n", target4);
    }

    return 0;
}
*/

登录后复制

为什么在二分查找中选择使用指针？

这其实是个很有意思的问题，因为在大多数情况下，用数组下标来实现二分查找，代码可能会更直观，也更不容易出错。那么，为什么还要用指针呢？我觉得，这更多是一种对底层机制的探索和理解。

从纯粹的性能角度看，现代编译器对下标访问和指针访问的优化能力都非常强，很多时候它们最终生成的机器码是高度相似的。也就是说，你可能很难在实际运行中，通过这种“指针优化”看到显著的速度提升。真正的价值在于：

直观的内存操作：当你使用指针时，你是在直接操作内存地址。
```
arr + i
```
登录后复制
实际上是告诉编译器“从
```
arr
```
登录后复制
指向的地址开始，跳过
```
i
```
登录后复制
个元素的大小，找到那个新地址”。这种思维方式对于理解内存布局、缓存局部性等概念非常有帮助。
C/C++的语言特性：在C/C++中，数组名本身就可以被视为一个指向其首元素的常量指针。所以，用指针来遍历或查找数组，某种程度上更符合语言的“哲学”。
避免下标越界：虽然指针操作本身也有越界的风险，但正确使用指针算术，比如
```
low + (high - low) / 2
```
登录后复制
这种方式，可以更清晰地表达你正在计算一个相对偏移量，而不是一个绝对的索引值，这在某些复杂场景下可能有助于减少因下标计算错误导致的bug。当然，这并不是说下标就一定容易错，只是换了一种思考方式。

我个人觉得，这更像是一种“手艺活”，让你能更细致地感受数据在内存中的流动。

指针版与索引版二分查找：性能差异与实际考量

关于性能，我得说实话，对于大多数应用场景和现代硬件来说，指针版的二分查找和基于索引（下标）的版本，在性能上几乎没有可感知的差异。这背后有几个原因：

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

编译器优化：现代C/C++编译器非常智能，它们会把你的数组下标操作（例如
```
arr[mid]
```
登录后复制
）优化成与指针操作（例如
```
*(arr + mid)
```
登录后复制
）几乎等价的机器指令。它们知道你最终都是在访问一个内存地址。
CPU缓存：二分查找的效率主要来源于其对数级的复杂度，以及它能很好地利用CPU缓存的局部性原理。无论你用指针还是索引，只要访问模式是连续的、可预测的，CPU都能很好地预取数据。
内存访问模式：指针和索引最终都归结为内存地址的计算。在二分查找中，我们跳跃式地访问数组元素，这本身就意味着不是完全线性的访问。每次计算
```
mid
```
登录后复制
对应的地址，无论是指针加减还是索引乘法，开销都非常小，远小于实际从内存中读取数据的时间。

所以，如果你是为了追求极致的性能，把希望寄托在“指针优化”上，那可能要失望了。真正的优化点往往在算法选择（比如，确定二分查找是最佳选择）、数据结构设计（数组是否适合）、以及如何避免不必要的内存访问等方面。

我倒是觉得，有时候指针版本在某些特定场景下，比如处理大内存块、或者当你已经有了指向某个数据块的指针而不是数组名时，可以显得更自然一些，少了一层“索引到指针”的转换。但这更多是代码风格和上下文的考量，而非普适的性能银弹。

使用指针进行查找的常见陷阱与最佳实践

用指针来玩转数组查找，确实能让你感受到C/C++的强大，但同时也要小心一些“坑”。

空指针或无效指针：这是最常见的问题。如果传入的
```
arr
```
登录后复制
是
```
NULL
```
登录后复制
，或者它指向的内存已经被释放、不再有效，那么任何解引用操作（
```
*mid
```
登录后复制
）都会导致程序崩溃（段错误）。我的代码里加了
```
if (arr == NULL || size == 0)
```
登录后复制
的检查，这是个好习惯。
指针越界：尽管二分查找的逻辑本身会限制指针在
```
[low, high]
```
登录后复制
范围内移动，但如果你在计算
```
mid
```
登录后复制
或者更新
```
low/high
```
登录后复制
时稍有不慎，比如
```
high = mid
```
登录后复制
而不是
```
high = mid - 1
```
登录后复制
，就可能导致死循环或者指针越界访问到数组外部。特别是
```
high = arr + size - 1
```
登录后复制
这一步，如果
```
size
```
登录后复制
是
```
0
```
登录后复制
，
```
size - 1
```
登录后复制
可能会导致负数，进而导致
```
arr - 1
```
登录后复制
这种非法地址，所以
```
size == 0
```
登录后复制
的检查非常重要。
指针类型不匹配：如果你查找的是
```
int
```
登录后复制
数组，但指针是
```
char*
```
登录后复制
类型，那么指针算术就会出错。
```
char* + 1
```
登录后复制
只会前进1个字节，而
```
int* + 1
```
登录后复制
会前进4个字节（假设int是4字节）。确保指针类型与数组元素类型一致。
未排序数组：二分查找的前提是数组必须是已排序的。如果你对一个未排序的数组使用二分查找，无论是指针版还是索引版，结果都是不可预测的。
整数溢出（在计算mid时）：虽然我的代码中
```
int* mid = low + (high - low) / 2;
```
登录后复制
这种写法可以有效避免
```
(low + high) / 2
```
登录后复制
在
```
low
```
登录后复制
和
```
high
```
登录后复制
都非常大时可能出现的整数溢出问题（当
```
low
```
登录后复制
和
```
high
```
登录后复制
是索引时更常见，但指针相减得到的是
```
ptrdiff_t
```
登录后复制
类型，再除以2，通常不会溢出）。不过，时刻保持这种警惕性是好的。

最佳实践方面：

边界条件检查：永远在函数入口处检查传入的指针是否为
```
NULL
```
登录后复制
，数组大小是否为
```
0
```
登录后复制
。
明确指针语义：清楚
```
low
```
登录后复制
和
```
high
```
登录后复制
指向的是什么。在我的实现里，
```
low
```
登录后复制
和
```
high
```
登录后复制
都指向数组内的有效元素。
测试极端情况：空数组、单元素数组、目标在数组开头、目标在数组结尾、目标不存在等。
代码清晰可读：虽然我们用指针，但代码逻辑依然要清晰，避免过度“炫技”导致难以理解和维护。