[C语言]二分查找

        进行二分查找的前提是在一个有序排列的数组中查找指定元素。

        例如，对一个升序排列的整型数组进行二分查找：

// 二分查找
// 参数1：arr--需要传入一个有序的、按升序排列（从小到大）的整型数组
// 参数2：len--数组的长度（数组的元素个数）
// 参数3：target--要查找的元素

// 返回值：返回找到的元素在数组中的下标（索引index），如果没有找到，则返回-1
int binary_search(int *arr, int len, int target)
{
    int left = 0; // 起始索引
    int right = len - 1; // 结束索引
    while (left <= right) // 如果起始索引和结束索引没有重合，继续查找
    {
        int mid = (left + right) / 2; // 中间索引，这么写能够防止整型溢出
        // 也可以写成 int mid = left + (right - left) / 2; 
        // 这两条代码是一样的

        if (arr[mid] == target)
        {
            // 如果找到了元素，返回索引
            return mid;
        }
        else if (arr[mid] < target)
        {
            // 如果当前的中间值小于要查找的目标元素，说明目标可能在右侧，
            // 需要调整左边界（起始索引）
            left = mid + 1;
        }
        else
        {
            // 如果当前的中间值大于要查找的目标元素，说明目标可能在左侧，
            // 需要调整右边界（结束索引）
            right = mid - 1;
        }
    }

    // 如果起始索引和结束索引重合了都没有找到目标元素，说明这个元素不在当前数组中，
    // 返回-1
    return -1;
}

原文地址：https://blog.csdn.net/bell00110100/article/details/137519241

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！