7-5 利用二分查找搜寻所有待查找数据
时间: 2023-04-18 15:00:41 浏览: 116
二分查找是一种高效的搜索算法,可以在有序数组中快速查找指定元素。如果要搜寻多个待查找数据,可以使用循环遍历数组,每次都进行一次二分查找。
具体步骤如下:
1. 将待查找数据按照升序排列,保证数组有序。
2. 遍历待查找数据,对于每个待查找数据,进行一次二分查找。
3. 在二分查找中,设定左右指针,初始时左指针指向数组第一个元素,右指针指向数组最后一个元素。
4. 每次将左右指针的中间位置作为查找的中间位置,比较中间位置的值与待查找数据的大小关系。
5. 如果中间位置的值等于待查找数据,则找到了该数据,返回其下标。
6. 如果中间位置的值大于待查找数据,则在左半部分继续查找,将右指针移动到中间位置的左侧。
7. 如果中间位置的值小于待查找数据,则在右半部分继续查找,将左指针移动到中间位置的右侧。
8. 重复步骤4-7,直到找到待查找数据或者左指针大于右指针,表示未找到该数据。
9. 如果找到了待查找数据,则记录其下标,继续查找下一个待查找数据。
10. 如果未找到待查找数据,则继续查找下一个待查找数据。
11. 遍历完所有待查找数据后,返回所有找到数据的下标。
需要注意的是,如果待查找数据中有重复元素,可能会出现多个下标,需要进行去重处理。
相关问题
jmu-c-二分查找
二分查找(Binary Search)是一种在有序数组中查找某一特定元素的搜索算法。它的思想是将数组分成两个部分,判断要查找的元素在哪一部分中,然后递归地在该部分中查找,直到找到该元素或者确定该元素不存在为止。
在C语言中,可以使用以下代码实现二分查找:
```c
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 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。
6-3 二分查找
二分查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将要查找的区间不断缩小为原来的一半,直到找到目标元素或者区间为空。
二分查找的时间复杂度为 O(log n),比线性查找更加高效。但是,它要求数组必须是有序的,而且对于插入和删除操作会导致数组失序,需要重新排序。
下面是一个简单的二分查找的代码实现:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,arr 是一个有序数组,target 是要查找的目标元素。我们用 left 和 right 分别表示当前查找的区间的左右边界,每次取区间中间的位置 mid 进行比较,如果等于目标元素,则返回 mid,如果小于目标元素,则将左边界移动到 mid+1,如果大于目标元素,则将右边界移动到 mid-1。如果最终没有找到目标元素,则返回 -1。