给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
时间: 2023-03-23 18:02:21 浏览: 92
以下是Python的代码实现:
```python
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
这是一个经典的二分查找算法。首先对整个数组进行二分,找到中间元素,如果中间元素等于目标值,则直接返回该元素的下标;如果中间元素小于目标值,则在右半部分继续查找;如果中间元素大于目标值,则在左半部分继续查找。每次缩小查找范围直到找到目标值或者查找范围为空。
在本题中,如果目标值存在于数组中,则返回其下标;否则返回-1。
相关问题
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
### 回答1:
题目描述:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
解题思路:由于数组是有序的,可以使用二分查找的方法来查找目标值。具体步骤如下:
1. 定义左右指针 left 和 right,分别指向数组的第一个元素和最后一个元素。
2. 当 left <= right 时,执行以下操作:
a. 计算中间位置 mid = (left + right) / 2。
b. 如果 nums[mid] == target,返回 mid。
c. 如果 nums[mid] < target,说明目标值在右半部分,将 left 更新为 mid + 1。
d. 如果 nums[mid] > target,说明目标值在左半部分,将 right 更新为 mid - 1。
3. 如果循环结束仍未找到目标值,返回 -1。
代码如下:
```
def search(nums, target):
left, right = , len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
时间复杂度:O(logn)。
空间复杂度:O(1)。
### 回答2:
题目翻译就是要实现一个函数,在给定的升序整型数组nums中查找目标值target,如果找到了则返回该目标值在数组中的下标,否则返回-1。
我们可以采用二分查找来实现该函数,具体过程如下:
首先定义两个指针left和right,分别指向数组nums的起始位置和终止位置;
计算数组的中间位置mid,若中间位置的数值等于目标值target,则返回该中间位置的下标;
若中间位置的数值小于目标值target,则目标值只可能在数组的右半部分中,因此将left指针指向mid+1的位置;
若中间位置的数值大于目标值target,则目标值只可能在数组的左半部分中,因此将right指针指向mid-1的位置。
重复以上步骤,直到在数组nums中找到目标值target或者left>right为止。
最后,如果未找到目标值target,则返回-1。
具体代码实现如下:
```python
def search(nums, target):
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
以上就是本题的解答过程和代码实现。二分查找时间复杂度为O(log2n),因此该函数的时间复杂度为O(log2n)。
### 回答3:
这道题目可以使用二分查找算法来解决。二分查找算法是一种在包含有序元素的数据集合中查找某一特定元素的搜索算法。它的主要思想是将一个有序的集合分成两半,然后判断要查找的元素在哪一半,并继续在该半进行二分查找,直到找到该元素或找不到为止。这种算法的时间复杂度为O(logn),较高效。
对于这道题目,我们可以将给定的有序数组nums分成两半,查找目标值target在哪一半,并继续在该半进行查找,直到找到该元素或找不到为止。具体的实现过程可以按如下步骤进行:
1. 定义左、右指针,左指针初始值为0,右指针初始值为nums数组的长度减1;
2. 进入循环,每次迭代时都将数组分成两半,找到中间元素的下标mid,判断中间元素是否等于目标值target。如果中间元素等于目标值,则返回中间元素的下标;如果中间元素大于目标值,则说明目标值应该在nums数组左半部分,将右指针移动到mid-1的位置;如果中间元素小于目标值,则说明目标值应该在nums数组右半部分,将左指针移动到mid+1的位置;
3. 循环结束的条件是左指针大于右指针,此时如果还没有找到目标值,则说明目标值不存在,返回-1。
完整的代码如下:
```
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
关于时间复杂度,可以看出只需要进行logn次比较,因此时间复杂度为O(logn),算法较高效。
用C++实现给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
好的,这是一个简单的二分查找问题,在 C++ 中可以这样实现:
```c++
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 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;
}
```
这个函数接受一个有序的整型数组 `nums` 和一个目标值 `target`,在 `nums` 中查找 `target`。如果找到了,返回对应的下标;否则返回 -1。
函数首先初始化左右指针 `left` 和 `right` 分别为数组的第一个和最后一个元素的下标。然后进入循环,只要 `left` 没有超过 `right`,就一直查找。
在循环中,首先计算中间元素的下标 `mid`。如果 `nums[mid]` 等于 `target`,说明找到了,直接返回 `mid`。如果 `nums[mid]` 小于 `target`,说明 `target` 在 `mid` 的右侧,将 `left` 更新为 `mid + 1`。如果 `nums[mid]` 大于 `target`,说明 `target` 在 `mid` 的左侧,将 `right` 更新为 `mid - 1`。
如果循环结束仍然没有找到 `target`,说明 `target` 不在数组中,返回 -1。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)