题解 | #二分查找-I#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param target int整型
# @return int整型
#

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # write code here
        index = sorted(range(len(nums)), key=lambda x: nums[x], reverse=False)  # 记录原序列位置索引
        nums = sorted(nums)  # 对原序列升序排序
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            midValue = nums[mid]
            if midValue < target:
                left = mid + 1
            elif midValue > target:
                right = mid - 1
            else:
                return index[mid]  # 返回 index 对应位置索引值，即为原序列位置索引
        return -1

# class Solution:
#     def search(self, nums: List[int], target: int) -> int:
#         # write code here
#         if len(nums) > 0:
#             left = 0
#             right = len(nums) - 1
#             while left <= right:
#                 mid = (left + right) // 2
#                 if nums[mid] == target:
#                     return mid
#                 elif nums[mid] < target:
#                     left = mid + 1
#                 else:
#                     right = mid - 1
#         return -1

#################################################################################################

# """ 二分查找法升级，对任意有序无序序列查位置索引 """
def binarySearch(a: [str, list], target: [int, str]) -> int:
    index = sorted(range(len(a)), key=lambda x: a[x], reverse=False)  # 记录原序列位置索引
    a = sorted(a)  # 对原序列升序排序
    left = 0
    right = len(a) - 1
    while left <= right:
        mid = (left + right) // 2
        midValue = a[mid]
        if midValue < target:
            left = mid + 1
        elif midValue > target:
            right = mid - 1
        else:
            return index[mid]  # 返回 index 对应位置索引值，即为原序列位置索引
    return -1


# """ 二分查找法，对去重列表查指定数据位置索引 """ 缺点输入序列必须是升序排列
def search(nums: list[int], target: int):
    N = 0
    if len(nums) > 0:
        left = 0
        right = len(nums) - 1
        while left <= right:
            N += 1  # 统计查询次数
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return [target, mid, N]  # 若存在返回：查询值，查询值位置索引，二分查找次数  最大值为：int(1 + math.log2(len(li)))，最小值为：1
    return -1, N  # 若不存在返回：-1，二分查找次数  最大值为：int(math.log2(1 + len(li))


# 例子：
# li = [-1, 0, 3, 4, 6, 10, 13, 14]
# for j in li:
#     o = search(li, 14)
#     print(o, '存在---最大查询次数：', int(1 + math.log2(len(li))))  # 查询数在列表最右侧，查询次数最大
#
# for k in li:
#     o = search(li, -1)
#     print(o, '不存在---最大查询次数：', int(math.log2(len(li) + 1)))  # 查询数在列表不存在，查询次数次于查询数在列表最右侧