二分查找-递归、迭代

数据结构应该是有序数组，下面写法是升序数组且无重复元素

class BinarySearch:
    
    @staticmethod
    def binary_search(arr: list[int], target):
        start = 0
        end = len(arr) - 1
        while start <= end:
            mid = start + ((end - start) >> 1)
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return None
    
    @staticmethod
    # 将区间在每次递归时更新，所以要将区间范围，在形式参数中指定
    def binary_search_recursion(arr: list[int], target, start, end):
        if start > end:
            return None
        mid = start + ((end - start) >> 1)
        if arr[mid] == target:
            print(mid)
            return mid
        elif arr[mid] < target:
            # 这里不带return会导致最底层递归获取到的mid无法接收。当然如果把mid放到一个可以存储的空间中也是可以的
            return BinarySearch.binary_search_recursion(arr, target, mid + 1, end)
        else:
            return BinarySearch.binary_search_recursion(arr, target, start, mid - 1)
            
if __name__ == '__main__':
    index = BinarySearch.binary_search([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12], 7)
    print(index)
    index = BinarySearch.binary_search_recursion([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12], 6, 0, 12)
    print(index)