在线性表L中进行二分查找,要求L
时间: 2023-07-19 07:04:02 浏览: 209
陈越、何钦铭-数据结构作业1:二分查找算法
是有序的。二分查找是一种高效的查找算法,其时间复杂度为O(logn)。
二分查找的过程如下:
1.首先确定整个查找区间的中间位置mid=(low+high)/2;
2.用待查关键字值与中间位置关键字值进行比较;
3.若相等,则查找成功并返回此位置;
4.若大于,则在后半部分继续进行折半查找;
5.若小于,则在前半部分继续进行折半查找;
6.重复以上步骤,直到查找成功或查找结束。
具体实现如下:
```python
def binary_search(L, target):
low = 0
high = len(L) - 1
while low <= high:
mid = (low + high) // 2
if L[mid] == target:
return mid
elif L[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
```
其中,L为有序线性表,target为待查找的值。如果找到了目标值,则返回其在线性表中的下标,否则返回-1。
阅读全文