二分法总结参考：
http://blog.csdn.net/ebowtang/article/details/50770315
精髓就是确定两个指针以及两个指针如何移动，注意二分法的一些变种。
33、Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
start, end = 0, len(nums) - 1
while start <= end:
mid = (start + end) / 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[start]:
if target >= nums[start] and target < nums[mid]:
end = mid - 1
else:
start = mid + 1
else:
if target > nums[mid] and target <= nums[end]:
start = mid + 1
else:
end = mid - 1
# if start == end and target != nums[start]:
# return -1
return -1
有几个地方模糊，一是取等问题，三个地方都涉及到等号，还有就是对 start 和 end 重新赋值时 +- 1问题。
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] > nums[left]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < nums[left]:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
left += 1
return -1
34. Search for a Range
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].
这道题涉及到二分法中一些常用的变种，找到第一个与key值相等的元素下标以及找到最后一个与元素相等的元素下标。所以这道题的做法是运用两次二分法。
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if nums == []:
return [-1, -1]
start = self.findfirst(nums, target)
end = self.findlast(nums, target)
return [start, end]
def findfirst(self, nums, target):
start, end = 0, len(nums) - 1
while start + 1 < end: # 如果直接是 start < end 会导致死循环
mid = (start + end) / 2
if nums[mid] < target:
start = mid + 1
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
def findlast(self, nums, target):
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) / 2
if nums[mid] > target:
end = mid - 1
else:
start = mid
if nums[end] == target:
return end
if nums[start] == target:
return start
return -1
对比下面方法：
int searchFirstEqual(int *arr, int n, int key)
{
int left = 0, right = n-1;
while(left < right)//根据两指针的意义，如果key存在于数组，left==right相等时已经得到解
{
int mid = (left+right)/2;
if(arr[mid] > key)//一定在mid为止的左边，并且不包含当前位置
right = mid - 1;
else if(arr[mid] < key)
left = mid + 1;//一定在mid位置的右边，并且不包括当前mid位置
else
right=mid;
}
if(arr[left] == key)
return left;
return -1;
}
int searchLastEqual(int *arr, int n, int key)
{
int left = 0, right = n-1;
while(left<right-1) {
int mid = (left+right)/2;
if(arr[mid] > key)
right = mid - 1;//key一定在mid位置的左边，并且不包括当前mid位置
else if(arr[mid] < key)
left = mid + 1; //key一定在mid位置的右边，相等时答案有可能是当前mid位置
else
left=mid;//故意写得和参考博客不一样，见下面证明
}
if( arr[left]<=key && arr[right] == key)
return right;
if( arr[left] == key && arr[right] > key)
return left;
return -1;
}
上面两种方法都易于理解，需要注意的有以下几点：循坏结束条件。判断循环结束条件关键要看指针移动情况。
1、 找到key值相等的元素
指针移动：end = mid - 1 和 start = mid + 1，还有一个判断条件，因为重新赋值都会有一个变化，因此start<=end不会死循环并且可以完整遍历。
2、找到第一个key值相等的元素
指针移动： start = mid + 1, end = mid，而mid是向下取整，当有一个取值没有变时，若循环条件是start<=end（最终判断数组为1个元素）就会进入死循环，因为一直赋值。而考虑start<end（最终判断数组是两个元素），符合避免死循环条件。但需要对这两个元素再次判断。
3、找到最后一个与key值相等的元素
指针移动： start = mid, end = mid - 1，关键还是要注意mid赋值是向下取整，如果start<end，则最后两个元素还是会进入死循环，因此条件为start + 1 < end。
还要注意溢出问题，一般不会写成mid = (start + end) / 2，而是mid = start + ( end - start ) / 2
其他解法：
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# Find the first idx where nums[idx] >= target
left = self.binarySearch(lambda x, y: x >= y, nums, target)
if left >= len(nums) or nums[left] != target:
return [-1, -1]
# Find the first idx where nums[idx] > target
right = self.binarySearch(lambda x, y: x > y, nums, target)
return [left, right - 1]
def binarySearch(self, compare, nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid
else:
left = mid + 1
return left
def binarySearch2(self, compare, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid - 1
else:
left = mid + 1
return left
def binarySearch3(self, compare, nums, target):
left, right = -1, len(nums)
while left + 1 < right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid
else:
left = mid
return left if left != -1 and compare(nums[left], target) else right
35、Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
题意本质为找到第一个大于或等于该key的元素位置。
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
start, end = 0, len(nums) - 1
while start < end:
mid = start + (end - start) / 2
if nums[mid] < target:
start = mid + 1
else:
end = mid
if nums[start] >= target:
return start
if nums[end] >= target:
return end
else:
return end + 1
74、 Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
row = len(matrix)
if row == 0:
return False
cow = len(matrix[0])
if cow == 0:
return False
temp = []
for i in xrange(row):
temp.append(matrix[i][cow-1])
print temp
res = self.first_not_less_than(temp, target)
print res
if res is True:
return True
elif res is False:
return False
else:
return self.first_not_less_than(matrix[res], target) is True
def first_not_less_than(self, nums, target):
start, end = 0, len(nums) - 1
while start < end:
mid = start + (end - start) / 2
if nums[mid] < target:
start = mid + 1
else:
end = mid
if nums[start] == target:
return True
elif nums[start] > target:
return start
else:
return False
if __name__ == '__main__':
s = Solution()
print s.searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,50]],3)
需要注意两个问题，一是
row = len(matrix)
if row == 0:
return False
cow = len(matrix[0])
if cow == 0:
return False
不能直接一步写成 row, cow = len(matrix), len(matrix[0])，然后判断。
二是注意 res == True 和 res is True的区别，本题中不能用 res == True.
==只是判断两者的值是不是相等，而True代表的值是1，False代表0，is就是要求两者结构必须一样。
81、 Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
这道题是33题的变种，需要多考虑一种情况，即中点和边界值相等。
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if nums == []:
return False
start, end = 0, len(nums) - 1
while start < end:
mid = start + (end - start) / 2
if nums[mid] == target:
return True
if nums[mid] > nums[start]:
if nums[mid] >= target and nums[start] <= target:
end = mid
else:
start = mid + 1
elif nums[mid] < nums[start]:
if nums[mid] <= target and nums[end] >= target:
start = mid
else:
end = mid - 1
else:
start += 1
if nums[start] == target or nums[end] == target:
return True
return False
153. Find Minimum in Rotated Sorted Array
在一个旋转后的数组中找到最小的元素。这里有一点需要注意，就是将中点值与end处值进行比较更方便，如果是和start值进行比较处理较麻烦。
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] > nums[end]:
start = mid + 1
else:
end = mid
return min(nums[start], nums[end])
162、 Find Peak Element
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
很多解法都说用二分法，但由于序列是无序的，用二分法的依据在于：
首先我们找到中间节点mid，如果大于两边返回当前的index就可以了，如果左边的节点比mid大，那么我们可以继续在左半区间查找，这里面一定存在一个peak，为什么这么说呢？假设此时的区间范围为[0,mid-1]，因为num[mid-1]一定大于num[mid]，如果num[mid-2]<=num[mid-1]，那么num[mid-1]就是一个peak。如果num[mid-2]>num[mid-1]，那么我们就继续在[0,mid-2]区间查找，因为num[-1]为负无穷，所以我们最终绝对能在左半区间找到一个peak。同理右半区间一样。
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
start, end = 0, len(nums) - 1
while start < end:
mid1 = start + (end - start) / 2
mid2 = mid1 + 1
if nums[mid1] < nums[mid2]:
start = mid2
else:
end = mid1
return start
还是要多理解，没有看起来这么简单。
79、 Two Sum II - Input array is sorted
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
for i in xrange(len(numbers) - 1):
if numbers[i] > target:
break
temp = self.binary_search(numbers, target - numbers[i], i+1)
if temp != -1:
return [i+1, temp+1]
return [-1, -1]
def binary_search(self, nums, target, start):
end =len(nums) - 1
while start <= end:
mid = start + (end - start) / 2
if nums[mid] == target:
return mid
if nums[mid] > target:
end = mid - 1
if nums[mid] < target:
start = mid + 1
return -1
209、Minimum Size Subarray Sum （滑动窗口）
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint
可以用滑动窗口思想去求解。
class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
sum, left = 0, 0
res = float('inf')
for i in xrange(len(nums)):
sum += nums[i]
while sum >= s:
res = min(res, i-left+1)
sum -= nums[left]
left += 1
return 0 if res == float('inf') else res
这种方法接触的还是比较少，需要进一步掌握理解。
278、First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
start, end = 1, n
while start < end:
mid = start + (end - start) / 2
if isBadVersion(mid):
end = mid
else:
start = mid + 1
return start
275、 H-Index II
Follow up for H-Index: What if the
citationsarray is sorted in ascending order? Could you optimize your algorithm?
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
length, res = len(citations), 0
start, end = 0, length - 1
while start <= end:
mid = start + (end - start) / 2
if length - mid <= citations[mid]:
res = max(length - mid,res)
end = mid - 1
else:
start = mid + 1
return res
简化：
def hIndex1(self,citations):
length, res = len(citations), 0
start, end = 0, length - 1
while start <= end:
mid = start + ((end - start) >> 1)
if length - mid <= citations[mid]:
end = mid - 1
else:
start = mid + 1
return length - start
287、 Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
start, end = 0, length - 1
nums = sorted(nums)
while start < end:
mid = start + (end - start) / 2
if nums[mid] >= mid + 1:
start = mid + 1
else:
end = mid
return start
上面二分法的思路不符合题意，要求不能修改数组。修改为：
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
start, end = 0, length - 1
while start <= end:
mid = start + (end - start) / 2
count = 0
for item in nums:
if item <= mid:
count += 1
if count > mid:
end = mid - 1
else:
start = mid + 1
return start
另一种思路，利用循环链表
