5 查找算法

约 262 字小于 1 分钟

2025-06-22

递归实现

/**
 * 二分查找(递归)
 * @param nums 待查找的数组
 * @param target 目标值
 * @param left 左边界
 * @param right 右边界
 * @return 目标值在数组中的索引，若不存在，则返回-1
 */
int binarySearchRecursive(const vector<int>& nums, int left, int right, int target) {
    int mid = (right - left) / 2 + left;
    if (nums[mid] == target) {
        return mid;
    }

    if (left > right) {
        return -1;
    }
    if (nums[mid] > target) {
        return binarySearchRecursive(nums, left, mid - 1, target);
    } else {
        return binarySearchRecursive(nums, mid + 1, right, target);
    }
}

非递归实现

/**
 * 二分查找(非递归)
 * @param nums 待查找的数组
 * @param target 目标值
 * @return 目标值在数组中的索引，若不存在，则返回-1
 */
int binarySearchIterative(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

int search(int* nums, int numsSize, int target) {
    if (nums == NULL || numsSize == 0)
        return -1;

    int left = 0, right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}