设计并编写一个二分查找算法
时间: 2023-09-10 16:09:14 浏览: 50
好的,以下是一个简单的二分查找算法的 Python 实现:
```
def binary_search(arr, target):
"""
在有序数组 arr 中查找 target,返回其索引值,若不存在则返回 -1
"""
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
```
该算法的时间复杂度为 O(log n),其中 n 为数组的长度。它的基本思想是通过比较中间值与目标值的大小关系,将查找范围逐渐缩小,直到找到目标值或者查找范围为空。
相关问题
用C语言设计并编写一个二分查找算法
好的,以下是一个简单的二分查找算法的 C 语言实现:
```
#include <stdio.h>
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = binary_search(arr, n, target);
if (result != -1) {
printf("Target %d found at index %d\n", target, result);
} else {
printf("Target %d not found in the array\n", target);
}
return 0;
}
```
该算法的时间复杂度为 O(log n),其中 n 为数组的长度。它的基本思想是通过比较中间值与目标值的大小关系,将查找范围逐渐缩小,直到找到目标值或者查找范围为空。
用Java编写一个二分查找算法
我可以为你提供一个参考示例:public static int binarySearch(int[] arr, int x) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)