数据结构二分查找算法代码
时间: 2024-05-24 21:08:30 浏览: 18
二分查找是一种基于比较目标值和数组中间元素的查找算法。在每次比较后,将查找范围缩小到数组的一半,直到找到目标值或者查找范围为空。
以下是二分查找算法的代码实现:
```c++
int binarySearch(int arr[], int left, int right, int target) {
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是待查找的有序数组,left和right是查找范围的左右边界,target是目标值。
相关问题
数据结构二分查找算法
二分查找是一种常见的搜索算法,用于在有序数组或有序列表中快速定位特定值的位置。这种算法的基本思想是将目标值与数组中间元素进行比较,根据比较结果将搜索范围缩小一半,直到找到目标值或确定目标值不存在为止。
以下是二分查找算法的基本步骤:
1. 初始化左边界 left 和右边界 right,分别指向数组的第一个元素和最后一个元素。
2. 计算中间位置 mid,可以使用公式 mid = (left + right) / 2。
3. 比较中间位置的值与目标值 target:
- 如果中间位置的值等于目标值,则找到目标值,返回索引。
- 如果中间位置的值大于目标值,则目标值可能在左半部分,更新右边界为 mid - 1。
- 如果中间位置的值小于目标值,则目标值可能在右半部分,更新左边界为 mid + 1。
4. 重复步骤 2 和步骤 3,直到找到目标值或搜索范围为空(即 left > right)。
以下是一个使用二分查找算法在有序数组中查找目标值的示例代码(使用递归实现):
```python
def binary_search(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, left, mid - 1)
else:
return binary_search(arr, target, mid + 1, right)
```
你可以将目标值、数组以及左右边界作为参数传递给该函数来执行二分查找。如果目标值存在于数组中,该函数将返回目标值的索引;否则,返回 -1 表示未找到。
希望这能回答你的问题!如有其他疑问,请随时提问。
数据结构二分查找算法c语言
引用中提到的二分查找算法是一种通过比较中间元素与目标元素来缩小查找范围的算法。它所以被称为“二分”,是因为每次查找都将查找范围分为两部分,然后再确定目标元素位于哪一部分,从而减少了查找的次数。
在二分查找算法中,首先需要确定查找范围的起始位置和结束位置,然后计算中间位置。通过比较中间位置的元素与目标元素的大小关系,可以进一步确定目标元素位于左半部分还是右半部分,从而缩小查找范围。如果中间元素等于目标元素,则查找成功;如果中间元素大于目标元素,则在左半部分继续查找;如果中间元素小于目标元素,则在右半部分继续查找。重复以上步骤,直到查找到目标元素或者确定目标元素不存在。
以下是一个使用C语言实现的二分查找算法的示例代码:
```c
#include <stdio.h>
int binary_search(int arr[], int n, int target) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
int arr[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
int n, addr;
printf("请输入待查找的关键字: ");
scanf("%d", &n);
addr = binary_search(arr, 11, n);
if (addr != -1) {
printf("查找成功,关键字 %d 所在的位置是: %d\n", n, addr);
} else {
printf("查找失败!\n");
}
return 0;
}
```
以上代码中,`binary_search`函数接受一个已排序的数组、数组的大小和目标元素作为参数,并返回目标元素在数组中的位置(如果存在),否则返回-1。在`main`函数中,我们定义了一个已排序的数组`arr`,然后输入待查找的关键字,并调用`binary_search`函数进行查找,最后输出查找结果。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)