写一个二分查找的伪代码
时间: 2023-11-25 09:49:35 浏览: 30
以下是二分查找的伪代码:
输入 arr[] // 输入有序序列
binary_search(arr, begin, end, ele):
if begin > end: // [begin,end] 不存在时,返回一个错误值(比如 -1)
return -1
mid <- ⌊ begin + (end - begin) / 2 ⌋ // 找到 [begin,end] 区域内中间元素所在位置的下标
if ele == arr[mid]: // 递归的出口,即 ele 和中间元素的值相等
return mid
if ele < arr[mid]: // 比较 ele 和中间元素的值,进一步缩小搜索区域
return binary_search(arr, begin, mid - 1, ele)
else:
return binary_search(arr, mid + 1, end, ele)
其中,arr为有序序列,begin和end分别为搜索区间的起始和结束下标,ele为要查找的元素。函数返回查找到的元素下标,如果未找到则返回-1。
相关问题
二分查找的伪代码怎么写
以下是二分查找的伪代码:
```
1. 将查找范围的左右边界确定为low和high
2. while low <= high:
3. 将中间位置mid计算出来
4. 如果mid位置的值等于目标值,返回mid
5. 如果mid位置的值小于目标值,将low更新为mid+1
6. 如果mid位置的值大于目标值,将high更新为mid-1
7. 如果查找范围内没有目标值,返回-1
```
其中,第2步是一个循环,每次循环都会将查找范围缩小一半,直到找到目标值或者查找范围为空。
举个例子,如果要在下面这个数组中找到第一个大于等于12的数字的位置,可以按照以下步骤进行二分查找:
```
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
low = 0
high = len(arr) - 1
target = 12
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
```
根据上述代码,可以得到第一个大于等于12的数字的位置为6。
用伪代码写出二分搜索的算法过程
当然,我很清楚您的要求。下面是二分搜索的算法伪代码示例:
```python
BinarySearch(arr, left, right, x):
# 确定中间元素
mid = (left + right) // 2
# 如果中间元素等于要查找的元素,则返回索引值
if arr[mid] == x:
return mid
# 如果中间元素大于要查找的元素,则在左半边递归查找
elif arr[mid] > x:
return BinarySearch(arr, left, mid-1, x)
# 如果中间元素小于要查找的元素,则在右半边递归查找
else:
return BinarySearch(arr, mid+1, right, x)
```
注:这里是基于递归实现的二分查找算法,其中 `arr` 是要查找的数组, `left` 是起始查找位置, `right` 是结束查找位置, `x` 是要查找的元素。在递归中,我们将数组划分为两个部分并查找其中一个子数组,直到查找到该元素。如果未找到该元素,则返回 `-1` 作为结果。