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 代码：

相关问题

实现对有序数组二分查找

二分查找是一种高效的查找算法，适用于有序数组。它通过将数组分成两部分，并与目标值进行比较，从而确定目标值在哪一部分中。以下是实现有序数组二分查找的步骤：

1. 初始化左指针left为数组的起始位置，右指针right为数组的结束位置。
2. 计算中间位置mid，可以使用公式mid = (left + right) / 2。
3. 比较中间位置的元素与目标值的大小：
- 如果中间位置的元素等于目标值，则找到了目标值，返回中间位置。
- 如果中间位置的元素大于目标值，则目标值可能在左半部分，更新右指针right为mid - 1。
- 如果中间位置的元素小于目标值，则目标值可能在右半部分，更新左指针left为mid + 1。
4. 重复步骤2和步骤3，直到找到目标值或者左指针大于右指针。

如果找到了目标值，返回其索引；如果没有找到，返回-1表示未找到。

用python实现二维有序数组查找。写出代码及思路

二维有序数组查找是一个常见的算法问题，可以使用双指针或二分查找的方式进行解决。下面介绍两种方法的实现。

方法一：双指针

如果二维数组是有序的，我们可以使用双指针的方式进行查找。具体的思路如下：

1. 定义两个指针row和col，分别指向二维数组的右上角。

2. 比较指针所指向的元素与目标元素的大小关系，如果相等，则返回True；如果指针所指向的元素小于目标元素，则说明目标元素在当前元素所在的列下方，将row加1；如果指针所指向的元素大于目标元素，则说明目标元素在当前元素所在的行左侧，将col减1。

3. 重复执行步骤2，直到找到目标元素或指针越界。

下面是Python代码的实现：

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1
    return False

这个函数的参数matrix是一个二维有序数组，target是要查找的目标元素。首先判断matrix是否为空，如果是则直接返回False。然后获取二维数组的行数m和列数n，将row指向0，将col指向n-1。进入循环，每次比较matrix[row][col]与target的大小关系，如果相等，则返回True。如果matrix[row][col]小于target，则说明目标元素在当前元素所在的列下方，将row加1。如果matrix[row][col]大于target，则说明目标元素在当前元素所在的行左侧，将col减1。最后如果没有找到目标元素，则返回False。

方法二：二分查找

如果二维数组的每一行都是有序的，我们可以使用二分查找的方式进行查找。具体的思路如下：

1. 对每一行进行二分查找，找到目标元素所在的行。

2. 在目标行上使用二分查找，找到目标元素。

下面是Python代码的实现：

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m - 1
    while left <= right:
        mid = (left + right) // 2
        if matrix[mid][0] <= target <= matrix[mid][n-1]:
            row = mid
            break
        elif matrix[mid][0] > target:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return False
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        if matrix[row][mid] == target:
            return True
        elif matrix[row][mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

这个函数的参数matrix是一个二维有序数组，target是要查找的目标元素。首先判断matrix是否为空，如果是则直接返回False。然后获取二维数组的行数m和列数n，将left指向0，将right指向m-1。进入循环，每次计算中间位置mid，如果matrix[mid][0]小于等于target且matrix[mid][n-1]大于等于target，则说明目标元素在第mid行，将row指向mid，跳出循环。如果matrix[mid][0]大于target，则说明目标元素在第mid行的上方，将right指向mid-1。如果matrix[mid][n-1]小于target，则说明目标元素在第mid行的下方，将left指向mid+1。最后如果没有找到目标元素，则返回False。

然后使用left指向0，使用right指向n-1，对第row行进行二分查找，判断matrix[row][mid]与target的大小关系，调整left和right的位置。最后如果找到目标元素，则返回True，否则返回False。