python二分法

tencentma

Python 二分查找，大佬帮忙看看下面的代码，为何啥返回也没有，谢谢。


#@brief binarySearch

#@Param a：待查找序列

#@param n：数组元素个数

#@param target：待查找目标元素

# @return：失败返回-1，成功返回数组索引

def binarySearch(a , n , target):

    mid = 0

    low = 0

    high = n - 1

    while low <= high :

        mid = (low + high) /2

# 将浮点型转换为整型

    mid = int(mid)

    if a[mid] == target:

        return mid

    elif a[mid] > target:

        high = mid - 1

    else:

        low = mid + 1

    return -1

a = [1,3,6,12,21,29,31,46,57,88,99];

index = binarySearch(a ,11 ,88);

print( index )

qzh阑珊梦

代码整体看起来没问题 可能是while循环那里只有mid = (low + high) /2这一条代码（缩进的问题） 还有 数组长度n可以用len（a）代替 一般不自己写数组长度

leonrein

[Python] 纯文本查看 复制代码

def binarySearch(a, target):
    mid = 0
    low = 0
    high = len(a) - 1

    while low <= high:
        mid = (low + high) // 2
        if a[mid] == target:
            return mid
        elif a[mid] > target:
            high = mid - 1
        else:
            low = mid + 1

    return -1


a = [1, 3, 6, 12, 21, 29, 31, 46, 57, 88, 99]  # 11

index = binarySearch(a, 88)
print(f"index-> {index}, corresponding target-> {a[index]};")

return -1 的缩进错误导致逻辑有问题.

qylisten

python代码发上来必须编辑好，它的排版错了可能找不到头绪了。

tencentma

[Python] 纯文本查看 复制代码

#python二分法
#low mid high  mid=(low+high)//2,都是下标
#若mid=target,return mid;若mid>target,high=mid-1;若mid<target,low=mid+1
def erfenfa(arr,target):
    low=0
    high=len(arr)-1
    mid=(low+high)//2
    while low<=high:
        if arr[mid]==target:
            return mid
        elif arr[mid]<target:
            low=mid+1
        else:
            high=mid-1
    return -1
arr=[2,7,12,15,24,56,78,98]
print(erfenfa(arr,56))

tencentma

tencentma 发表于 2022-9-12 10:04
[mw_shl_code=python,true]#python二分法
#low mid high  mid=(low+high)//2,都是下标
#若mid=target,ret ...

@leonrein @qzh阑珊梦 大神帮忙看看我这个，我注意缩进了，但是打印出来还是啥都没有。

Wisdom_xiaogui

这代码没有问题，可能是自己的环境没有配对。 // 就代表整除了。或者你换为
mid = (low + high) /2
mid=int(mid)
虽说是多此一举。

qzh阑珊梦

tencentma 发表于 2022-9-12 10:05
@leonrein @qzh阑珊梦 大神帮忙看看我这个，我注意缩进了，但是打印出来还是啥都没有。

把mid=(low+high)//2放在while里面  你的代码相当于mid值不变 死循环了 二分法是要mid值一直变