最全的二分查找模板请到：https://blog.csdn.net/qq_19446965/article/details/82184672
在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回 -1。
样例 1：
输入：nums = [1,2,2,4,5,5], target = 2
输出：1 或者 2
样例 2：
输入：nums = [1,2,2,4,5,5], target = 6
输出：-1
练习地址：https://www.lintcode.com/problem/classical-binary-search/description
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
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left)//2
if nums[mid] == target:
return mid
elif target > nums[mid]:
left = mid + 1
else:
right = mid - 1
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， 返回-1
练习地址：https://www.lintcode.com/problem/first-position-of-target/descriptionclass 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):
if nums and target > nums[-1]:
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left)//2
if target > nums[mid]:
left = mid + 1
else:
right = mid - 1
if nums[left] == target:
return left
return -1
代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。
n = 5:
isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true
因此可以确定第四个版本是第一个错误版本。class Solution:
"""
@param n: An integer
@return: An integer which is the first bad version.
"""
def findFirstBadVersion(self, n):
left = 1
right = n
while left <= right:
mid = left + (right - left)//2
if not SVNRepo.isBadVersion(mid):
left = mid + 1
else:
right = mid - 1
return left
练习地址：https://www.jiuzhang.com/solutions/first-bad-version/#tag-highlight-lang-python
【题目4】
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回[-1, -1]
例1:
输入:
[]
9
输出:
[-1,-1]
例2:
输入:
[5, 7, 7, 8, 8, 10]
8
输出:
[3, 4]class Solution:
"""
@param A: an integer sorted array
@param target: an integer to be inserted
@return: a list of length 2, [index1, index2]
"""
def searchRange(self, A, target):
# write your code here
nums = A
if nums and (target > nums[-1] or target < nums[0]):
return [-1, -1]
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left)//2
if nums[left] == target and nums[right] == target:
return [left, right]
if target > nums[mid]:
left = mid + 1
elif target < nums[mid]:
right = mid - 1
elif target > nums[left]:
left += 1
elif target < nums[right]:
right -= 1
return [-1, -1]
练习地址：https://www.lintcode.com/problem/search-for-a-range/description
倍增
https://www.jiuzhang.com/solutions/search-in-a-big-sorted-array/
https://www.lintcode.com/problem/search-a-2d-matrix-ii/description
https://www.lintcode.com/problem/smallest-rectangle-enclosing-black-pixels/description
原文：https://www.cnblogs.com/rnanprince/p/11743414.html