1158 有序数组的查找

题目描述：

给定一个有序数组 nums，如果其中一个数 target 存在，则返回其索引。否则，返回 target按顺序插入的索引。

示例1：

输入: nums = [1,3,5,6], target = 5
输出: 2

示例2：

输入: nums = [1,3,5,6], target = 2
输出: 1

解题思路：

这道题要求我们在一个有序数组中查找 target 的位置。如果 target 存在，则返回其索引；否则，返回 target 按顺序插入的索引。

我们可以使用二分查找算法来解决这个问题。首先，我们初始化左指针 left 和右指针 right。然后，在 while 循环中，我们计算中间元素的索引 mid，并比较 nums[mid] 与 target。如果 nums[mid] < target，则说明 target 应该在 mid 的右侧，因此我们将 left 置为 mid + 1。如果 nums[mid] > target，则说明 target 应该在 mid 的左侧，因此我们将 right 置为 mid - 1。如果 nums[mid] = target，则说明 target 已经存在于数组中，直接返回 mid 即可。

如果 while 循环结束时仍然没有找到 target，则说明 target 不存在于数组中，此时我们只需要返回 left 即可。

代码实现：

Python 代码：

相关问题

C++实现一个算法在一个有序数组中查找一个元素

可以使用二分查找算法在有序数组中查找一个元素。

二分查找算法的基本思想是：不断将有序数组的中间元素与目标元素进行比较，根据比较结果缩小查找范围，直到找到目标元素或者确定目标元素不存在。

C++代码实现如下：

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 目标元素不存在
}

其中，`arr`是有序数组，`n`是数组长度，`target`是要查找的目标元素。函数返回目标元素在数组中的下标，如果目标元素不存在则返回-1。