特定二分搜索:给定一个有序正整数数组和一个要查找的目标数。要求给出要查找目标数在给定数组中第一次(或最后一次)出现的索引号(数组下标),没有查找到时输出-1。
时间: 2023-06-08 12:03:45 浏览: 97
好的,这是一个技术问题,我可以回答。这个问题可以使用特定的二分搜索算法来解决,时间复杂度为O(log n)。具体实现步骤是,定义左右指针,分别指向数组的头部和尾部,之后计算出中间值,判断目标数与中间值的大小关系,如果目标数小于中间值,则在左半边继续搜索,否则在右半边搜索。直到找到目标数为止,若找不到则返回-1。在查找过程中,可以通过一个变量记录目标数第一次出现的索引号,若要查找最后一次出现的索引号,则需要修改查找策略,具体可参考算法题解。
相关问题
请帮我用c语言写这道题的代码:给定一个有序正整数数组和一个要查找的目标数。要求给出要查找目标数在给定数组中第一次(或最后一次)出现的索引号(数组下标),没有查找到时输出-1。
好的,以下是代码:
```c
#include <stdio.h>
// 寻找第一次或最后一次出现的索引号
int binarySearch(int arr[], int n, int target, int isFirst) {
int left = 0, right = n - 1;
int ans = -1; // 初始化为-1,表示没找到
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) { // 找到目标数
ans = mid; // 更新答案
if (isFirst) { // 如果是寻找第一次出现的
right = mid - 1; // 向左移动右边界
} else { // 如果是寻找最后一次出现的
left = mid + 1; // 向右移动左边界
}
} else if (arr[mid] < target) { // 目标数在右半部分
left = mid + 1;
} else { // 目标数在左半部分
right = mid - 1;
}
}
return ans;
}
int main() {
int arr[] = {1, 2, 2, 2, 4, 5, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 2; // 要查找的目标数
int firstIndex = binarySearch(arr, n, target, 1); // 寻找第一次出现的索引号
int lastIndex = binarySearch(arr, n, target, 0); // 寻找最后一次出现的索引号
printf("第一次出现的索引号: %d\n", firstIndex);
printf("最后一次出现的索引号: %d\n", lastIndex);
return 0;
}
```
该代码中,`binarySearch` 函数使用二分查找法,在有序数组中寻找目标数第一次(或最后一次)出现的索引号。函数参数 `isFirst` 为布尔值,表示是否寻找第一次出现的索引号。如果该值为 `true`,则向左移动右边界,否则向右移动左边界。
在主函数中,我们先声明一个有序正整数数组 `arr` 和要查找的目标数 `target`,然后分别调用 `binarySearch` 函数,寻找第一次和最后一次出现的索引号,最后输出结果。
注意,该代码假设输入的数组已经有序。如果数组无序,需要先进行排序操作。
请帮我写这道题的代码:给定一个有序正整数数组和一个要查找的目标数。要求给出要查找目标数在给定数组中第一次(或最后一次)出现的索引号(数组下标),没有查找到时输出-1。
好的,这是一个简单的二分查找问题,以下是代码实现:
```python
def binary_search(arr, target, first=True):
left, right = 0, len(arr) - 1
res = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
res = mid
if first:
right = mid - 1
else:
left = mid + 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return res
# 在有序数组 arr 中查找 target 第一次出现的位置
def find_first_position(arr, target):
return binary_search(arr, target, True)
# 在有序数组 arr 中查找 target 最后一次出现的位置
def find_last_position(arr, target):
return binary_search(arr, target, False)
```
如果要查找 target 最后一次出现的位置,只需要修改 `find_first_position` 函数为 `find_last_position` 即可。