# ===== CodeLab: 二分查找:面试必会 =====
# 来源: https://aoerliang.dpdns.org/articles/algo-binary-search
# 以下代码片段按文章出现顺序拼接, 共 3 段

# ----- 片段 1 (python) -----
def binary_search(nums, target):
    left, right = 0, 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  # 未找到

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))  # -1

# ----- 片段 2 (python) -----
def find_left(nums, target):
    left, right = 0, len(nums) - 1
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans if ans != -1 and nums[ans] == target else -1

print(find_left([1, 2, 2, 2, 3, 4], 2))  # 1
print(find_left([1, 2, 3, 4], 5))        # -1

# ----- 片段 3 (python) -----
def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1   # 最小值在右半段
        else:
            right = mid      # 最小值在左半段(含 mid)
    return nums[left]

print(find_min([4, 5, 6, 1, 2, 3]))  # 1