# 1.二分法查找相同数# Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.# Your algorithm's runtime complexity must be in the order of O(log n).# If the target is not found in the array, return [-1, -1].# For example,# Given [5, 7, 7, 8, 8, 10] and target value 8,# return [3, 4].def bin_search(li, target): # 先利用二分法，匹配到mid。 # 开两个for循环，依次从mid往左和往右查找，直到第一个不等于TARGET的时候返回 low = 0 high = len(li) - 1 while low <= high: mid = (low + high) // 2 if li[mid] == target: a = mid b = mid while li[a] == target and a >= 0: # and 条件在最开始 a -= 1 while li[b] == target and b < len(li) - 1: b += 1 return (a + 1, b) elif li[mid] > target: high = mid - 1 else: low = mid + 1 return Noneprint(bin_search([1, 1, 3, 5, 6, 7, 8, 9, 10, 10], 10))# 2.# Given an array of integers,# return indices of the two numbers such that they add up to a specific target.# You may assume that each input would have exactly one solution,# and you may not use the same element twice.# Example# Given nums = [2, 7, 11, 15], target = 9,# Because nums[0] + nums[1] = 2 + 7 = 9,# return [0, 1].nums = [2, 7, 11, 15]def twoSum(nums, target): ''' 时间复杂度O(N**2), 两层循环，依次匹配 :param nums: :param target: :return: ''' for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return i, j return None# print(twoSum(nums, 18))def tow_sum_2(nums, target):# TODO：fOr 循环固定单个值， 用target - 固定值， 用二分法查待匹配的值。def two_sum_3(nums, target): # 列表有序，初始值 Sum = Num[low]+Num[high] # 从最左和最右移动索 low = 0 high = len(nums) - 1 while low < high: sum = nums[low] + nums[high] # 列表有序，初始 sum = 列表最小值+最大值 if sum > target: high -= 1 elif sum < target: low += 1 else: return low, high return -1, -1print(two_sum_3(nums, 22))# TODO：尝试目标值由三个数相加得来，返回三个下标。
