binary_search_special
二分法总结参考：
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 midif 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.这道题涉及到二分法中一些常用的变种，找到第一个与key值相等的元素下标以及找到最后一个与元素相等的元素下标。所以这道题的做法是运用两次二分法。
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].
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 -1def 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 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
其他解法：
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 leftdef 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 leftdef 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 Truedef 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 Falseif __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.这道题是33题的变种，需要多考虑一种情况，即中点和边界值相等。
(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.
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 = midreturn 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 thecitationsarray 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
【binary_search_special】另一种思路，利用循环链表
推荐阅读
- 前沿论文|论文精读（Neural Architecture Search without Training）
- ElasticSearch6.6.0强大的JAVA|ElasticSearch6.6.0强大的JAVA API详解
- Elasticsearch|Elasticsearch 简介
- elasticsearch分析器
- 三十一、|三十一、 Elasticsearch集群搭建部署及配置
- oh|oh my love
- springmvc|springmvc 集成 Spring Data Elasticsearch 遇到的坑
- Elasticsearch（一）什么是Elasticsearch
- elasticsearch|elasticsearch 7.0 新特性之 search as you type
- 开工第一课|开工第一课 | 用 DocArray 搭建 fashion search 引擎