二分搜索时间复杂度代码
时间: 2023-08-10 10:29:11 浏览: 52
二分搜索的时间复杂度为O(log n),代码如下:
```
int binarySearch(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
```
其中,arr为要查找的数组,low为数组中查找区间的起始下标,high为数组中查找区间的结束下标,target为要查找的目标值。在while循环中,计算出中间位置mid,如果该位置的值等于目标值,则返回mid;如果该位置的值小于目标值,则在右半部分继续查找,将low更新为mid+1;如果该位置的值大于目标值,则在左半部分继续查找,将high更新为mid-1。如果最终没有找到目标值,则返回-1。
相关问题
二分检索的时间复杂度
二分检索的时间复杂度为O(log n)。
二分检索是一种高效的搜索算法,它通过将已排序的数组分成两半来查找目标元素。每次比较中间元素与目标元素,如果中间元素等于目标元素,则返回该元素的索引;如果中间元素大于目标元素,则在左半部分继续搜索;如果中间元素小于目标元素,则在右半部分继续搜索。重复这个过程,直到找到目标元素或者确定目标元素不存在。
由于每次比较都将搜索范围减半,所以二分检索的时间复杂度为O(log n),其中n是数组的长度。
以下是一个使用二分检索查找目标元素的示例代码:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# 示例用法
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
result = binary_search(arr, target)
print("目标元素的索引:", result) # 输出:5
```
时间复杂度 计算复杂度
时间复杂度是用来描述算法运行时间的函数,通常使用大O符号表示。它不考虑低阶项和首项系数,只关注输入值大小趋近无穷时的情况。如果代码中全是常量,则时间复杂度为O(1)。当一个时间复杂度中有多个函数时,我们选择其中最高阶的算法作为时间复杂度。例如,如果一个算法的时间复杂度为O(n^2-n),我们简化为O(n^2)。[1][2]
举例来说,对于二分查找算法(BinarySearch),其时间复杂度为O(logn),其中n是输入数组的长度。这是因为在每次迭代中,算法将搜索范围缩小一半,直到找到目标元素或搜索范围为空。因此,时间复杂度随着输入规模的增加而以对数的方式增长。[3]
另一个例子是阶乘递归算法(Factorial),其时间复杂度为O(n),其中n是输入的大小。这是因为在每次递归调用中,算法将问题规模减小1,直到达到基本情况。因此,时间复杂度随着输入规模的增加线性增长。[4]
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)