python二分查找算法
时间: 2023-09-21 10:03:00 浏览: 46
二分查找算法通常用于有序的数组或列表中查找某个特定元素。具体实现过程如下:
1. 将目标数组或列表按升序或降序排列,假设升序排列;
2. 定义查找区间的左右边界 left 和 right,初始时 left=0,right=len(arr)-1;
3. 循环进行以下步骤,直到 left>right:
a. 计算中间元素的下标 mid=(left+right)//2;
b. 若目标元素等于 arr[mid],返回 mid;
c. 若目标元素小于 arr[mid],说明目标元素在左半部分,将 right=mid-1;
d. 若目标元素大于 arr[mid],说明目标元素在右半部分,将 left=mid+1;
4. 若循环结束,说明目标元素不存在,返回 -1。
如果你需要具体实现该算法,可以使用下面的 Python 代码:
```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 为目标元素。
相关推荐
![](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)