模板：
class Solution:
# @param nums: The integer array
# @param target: Target number to find
# @return the first position of target in nums, position start from 0
def binarySearch(self, nums, target):
if not nums:
return -1
start, end = 0, len(nums) - 1
# 用 start + 1 < end 而不是 start < end 的目的是为了避免死循环
# 在 first position of target 的情况下不会出现死循环
# 但是在 last position of target 的情况下会出现死循环
# 样例：nums=[1，1] target = 1
# 为了统一模板，我们就都采用 start + 1 < end，就保证不会出现死循环
while start + 1 < end:
# python 没有 overflow 的问题，直接 // 2 就可以了
# java和C++ 最好写成 mid = start + (end - start) / 2
# 防止在 start = 2^31 - 1, end = 2^31 - 1 的情况下出现加法 overflow
mid = (start + end) // 2
# > , =, < 的逻辑先分开写，然后在看看 = 的情况是否能合并到其他分支里
if nums[mid] < target:
# 写作 start = mid + 1 也是正确的
# 只是可以偷懒不写，因为不写也没问题，不会影响时间复杂度
# 不写的好处是，万一你不小心写成了 mid - 1 你就错了
start = mid
elif nums[mid] == target:
end = mid
else:
# 写作 end = mid - 1 也是正确的
# 只是可以偷懒不写，因为不写也没问题，不会影响时间复杂度
# 不写的好处是，万一你不小心写成了 mid + 1 你就错了
end = mid
# 因为上面的循环退出条件是 start + 1 < end
# 因此这里循环结束的时候，start 和 end 的关系是相邻关系（1和2，3和4这种）
# 因此需要再单独判断 start 和 end 这两个数谁是我们要的答案
# 如果是找 first position of target 就先看 start，否则就先看 end
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回 -1。
样例 1：
输入：nums = [1,2,2,4,5,5], target = 2
输出：1 或者 2
样例 2：
输入：nums = [1,2,2,4,5,5], target = 6
输出：-1
class Solution:
"""
@param nums: An integer array sorted in ascending order
@param target: An integer
@return: An integer
"""
def findPosition(self, nums, target):
# write your code here
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] == target:
end = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
给一个升序数组，找到 target 最后一次出现的位置，如果没出现过返回 -1
样例 1：
输入：nums = [1,2,2,4,5,5], target = 2
输出：2
样例 2：
输入：nums = [1,2,2,4,5,5], target = 6
输出：-1
class Solution:
"""
@param nums: An integer array sorted in ascending order
@param target: An integer
@return: An integer
"""
def lastPosition(self, nums, target):
# write your code here
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] == target:
start = mid
else:
end = mid
if nums[end] == target:
return end
if nums[start] == target:
return start
return -1
给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
样例 1:
输入:[1,4,4,5,7,7,8,9,9,10]，1
输出: 0
样例解释:
第一次出现在第0个位置。
样例 2:
输入: [1, 2, 3, 3, 4, 5, 10]，3
输出: 2
样例解释:
第一次出现在第2个位置
样例 3:
输入: [1, 2, 3, 3, 4, 5, 10]，6
输出: -1
样例解释:
没有出现过6， 返回-1class Solution:
"""
@param nums: The integer array.
@param target: Target to find.
@return: The first position of target. Position starts from 0.
"""
def binarySearch(self, nums, target):
# write your code here
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] == target:
end = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。
n = 5:
isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true
因此可以确定第四个版本是第一个错误版本。
调用 isBadVersion 的次数越少越好
请阅读代码编辑框内注释代码，获取对于不同语言正确调用 isBadVersion 的方法，比如java的调用方式是SVNRepo.isBadVersion(v)
#class SVNRepo:
# @classmethod
# def isBadVersion(cls, id)
# # Run unit tests to check whether verison `id` is a bad version
# # return true if unit tests passed else false.
# You can use SVNRepo.isBadVersion(10) to check whether version 10 is a
# bad version.
class Solution:
"""
@param n: An integer
@return: An integer which is the first bad version.
"""
def findFirstBadVersion(self, n):
# write your code here
start, end = 1, n
while start + 1 < end:
mid = (start + end) // 2
if SVNRepo.isBadVersion(mid):
end = mid
else:
start = mid
if SVNRepo.isBadVersion(start):
return start
if SVNRepo.isBadVersion(end):
return end
return -1
给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。
样例 1:
输入: A = [1, 2, 3], target = 2, k = 3
输出: [2, 1, 3]
样例 2:
输入: A = [1, 4, 6, 8], target = 3, k = 3
输出: [4, 1, 6]
O(logn + k) 的时间复杂度
class Solution:
"""
@param A: an integer array
@param target: An integer
@param k: An integer
@return: an integer array
"""
def kClosestNumbers(self, A, target, k):
# write your code here
if k <= 0:
return []
nearest_index = self.find_nearest(A, target)
return self.find_k_elements(A, target, k, nearest_index)
def find_nearest(self, nums, target):
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] == target:
end = mid
else:
end = mid
if (end >= len(nums)) or ((start >= 0) and abs(nums[start]-target) <= abs(nums[end]-target)):
return start
return end
def find_k_elements(self, A, target, k, nearest_index):
result = [A[nearest_index]]
i, j = nearest_index-1, nearest_index+1
while (i >= 0 or j < len(A)) and len(result) < k:
if j >= len(A) or (i >= 0 and abs(A[i]-target) <= abs(A[j]-target)):
result.append(A[i])
i -= 1
else:
result.append(A[j])
j += 1
return result
采用的是二分法 + 双指针
二分法确定一个位置，左侧是 < target，右侧是 >= target
然后用两根指针从中间向两边走，依次找到最接近的 k 个数
参考代码：
class Solution:
"""
@param A: an integer array
@param target: An integer
@param k: An integer
@return: an integer array
"""
def kClosestNumbers(self, A, target, k):
# 找到 A[left] < target, A[right] >= target
# 也就是最接近 target 的两个数，他们肯定是相邻的
right = self.find_upper_closest(A, target)
left = right - 1
# 两根指针从中间往两边扩展，依次找到最接近的 k 个数
results = []
for _ in range(k):
if self.is_left_closer(A, target, left, right):
results.append(A[left])
left -= 1
else:
results.append(A[right])
right += 1
return results
def find_upper_closest(self, A, target):
# find the first number >= target in A
start, end = 0, len(A) - 1
while start + 1 < end:
mid = (start + end) // 2
if A[mid] >= target:
end = mid
else:
start = mid
if A[start] >= target:
return start
if A[end] >= target:
return end
# 找不到的情况
return end + 1
def is_left_closer(self, A, target, left, right):
if left < 0:
return False
if right >= len(A):
return True
return target - A[left] <= A[right] - target
给一个按照升序排序的非负整数数组。这个数组很大以至于你只能通过固定的接口 ArrayReader.get(k) 来访问第k个数(或者C++里是ArrayReader->get(k))，并且你也没有办法得知这个数组有多大。
找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。
如果找不到target，返回-1。
样例 1:
输入: [1, 3, 6, 9, 21, ...], target = 3
输出: 1
样例 2:
输入: [1, 3, 6, 9, 21, ...], target = 4
输出: -1
O(logn)的时间复杂度，n是target第一次出现的下标。
"""
Definition of ArrayReader
class ArrayReader(object):
def get(self, index):
# return the number on given index,
# return 2147483647 if the index is invalid.
"""
class Solution:
"""
@param: reader: An instance of ArrayReader.
@param: target: An integer
@return: An integer which is the first index of target.
"""
def searchBigSortedArray(self, reader, target):
# write your code here
end = self.find_first_greater_index(reader, target)
return self.bin_search(reader, target, end)
def find_first_greater_index(self, reader, target):
i = 1
while reader.get(i) < target:
i = i*2
return i
def bin_search(self, reader, target, end):
start = 0
while start + 1 < end:
mid = (start + end) // 2
if reader.get(mid) < target:
start = mid
elif reader.get(mid) == target:
end = mid
else:
end = mid
if reader.get(start) == target:
return start
if reader.get(end) == target:
return end
return -1
精简下代码：
class Solution:
# @param {ArrayReader} reader: An instance of ArrayReader
# @param {int} target an integer
# @return {int} an integer
def searchBigSortedArray(self, reader, target):
# write your code here
index = 0
while reader.get(index) < target:
index = index * 2 + 1
start, end = 0, index
while start + 1 < end:
mid = start + (end - start) // 2
if reader.get(mid) < target:
start = mid
else:
end = mid
if reader.get(start) == target:
return start
if reader.get(end) == target:
return end
return -1
原文：https://www.cnblogs.com/bonelee/p/11749311.html