python二分搜索
时间: 2023-11-24 22:53:07 浏览: 39
二分搜索是一种在有序数组中查找特定元素的算法。它的基本思想是将数组分成两半,然后确定要查找的元素在哪一半中,然后继续在该半中查找,直到找到该元素或确定该元素不存在为止。以下是一个Python实现的二分搜索的例子:
```python
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
```
这个函数接受一个有序数组和要查找的元素作为参数,并返回元素的索引(如果存在)或-1(如果不存在)。
相关问题
python 二分搜索
好的,关于 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` 是要查找的目标值。函数返回目标值在列表中的下标,如果不存在则返回 `-1`。
python二分搜索迭代算法
二分搜索算法是一种高效的搜索算法,它可以在有序数组中定位特定元素时具有优势。Python中实现二分搜索算法的方法有两种,一种是迭代算法,另一种是递归算法。下面是Python二分搜索迭代算法的实现步骤:
1. 定义一个函数,输入参数为有序数组和要查找的元素。
2. 定义左右指针,分别指向数组的第一个和最后一个元素。
3. 当左指针小于等于右指针时,执行以下步骤:
a. 计算中间位置的索引值。
b. 如果中间位置的元素等于要查找的元素,返回该元素的索引值。
c. 如果中间位置的元素大于要查找的元素,将右指针移动到中间位置的左边一位。
d. 如果中间位置的元素小于要查找的元素,将左指针移动到中间位置的右边一位。
4. 如果没有找到要查找的元素,返回-1。
下面是Python代码实现:
```python
def binary_search_iterative(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
```