二分查找的线性表内容是:[1,3,5,7,9,2,4,6,8,10,11,13,15,17,19],请画出他的判定树图
时间: 2024-06-18 07:05:43 浏览: 18
二分查找是一种在有序数组中查找某一特定元素的搜索算法。对于给定的有序数组,采用二分查找的方法可以在时间复杂度O(log n)内找到目标元素。
对于线性表[1,3,5,7,9,2,4,6,8,10,11,13,15,17,19],要使用二分查找,需要先将其排序。排好序后,该线性表变为[1,2,3,4,5,6,7,8,9,10,11,13,15,17,19]。
二分查找的基本思路是:每次将待查找区间缩小一半,直到找到目标元素或者区间为空。具体实现可参考下面的代码:
```
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
该算法的判定树图如下所示:
```
10
/ \
/ \
5 15
/ \ / \
/ \ / \
3 7 13 17
/ \ / \ / \ / \
1 4 6 9 11 14 18 19
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)