class Solution(object):
def search(self, matrix, target):
"""
input: int[][] matrix, int target
return: int[]
"""
# write your solution here
if not matrix or len(matrix)==0:
return [-1,-1]
m, n = len(matrix), len(matrix[0])
left, right= 0, m*n-1
while left<=right:
mid = (left+right)//2
row = mid//n
column = mid%n
if matrix[row][column]==target:
return [row, column]
elif matrix[row][column]<target:
left = mid+1
else:
right = mid-1
return [-1,-1]
def binary_search (nums, target):
left=0
right=len(nums)-1
while left<=right:
mid=(left+right)/2
if nums[mid]>target:
right=mid
elif nums[mid]<target:
left=mid
else:
return mid
return None
本质是提前一步退出
搜索空间只剩下两个元素，target和谁更近就是谁
Post-processing 最后剩下LR还没有比较
正确做法
class Solution(object):
def closest(self, array, target):
"""
input: int[] array, int target
return: int
"""
# write your solution here
if not array or len(array)==0:
return -1
left, right = 0, len(array)-1
while left<right-1:
mid = (left+right)//2
if array[mid]==target:
return mid
elif array[mid]<target:
left = mid #不可以+1
else:
right = mid #不可以-1
return left if (array[right]-target>target-array[left]) else right
#上面这种写法虽然没有+1-1 但是肯定不会有死循环，因为while循环条件不同了，循环内一定是三个元素，
#所以不会在两个数之间来回传值
class Solution (object):
public int findClosest (int[] array, int target){
if (array==null||array.length==0){
return -1;
}
int l = 0;
int r = array.length-1;
while (l<r-1) {
int mid = l+(r-l)/2; //int越过32位的overflow 可能会变成负数，可能是一个奇怪的数，不会自动变成long
if (array[mid]==target) {
return mid;
}
elif (array[mid]<target) {
left = mid;
}
else {
right = mid;
}
}
return (array[right]-target<target-array[left])? right : left; //ternary operator
}
Time: O(logn)
First Occurrence
如果找不到，return-1 （面试时，注意和面试官沟通，回复-1还是None）
num[mid]<target, 左半边不要了，一定在右边，可以+1(left=mid+1)
num[mid]>target, 右半边不要了，一定在左边，但是含mid(right=mid)
num[mid]=target, 虽然找到了，但也有可能不是第一个，所以right=mid
class Solution(object):
def firstOccur(self, array, target):
"""
input: int[] array, int target
return: int
"""
# write your solution here
if not array or len(array)==0:
return -1
left, right = 0, len(array)-1
while left<right-1:
mid = (left+right)//2
if array[mid]==target:
right=mid
elif array[mid]<target:
left=mid+1
elif array[mid]>target:
right=mid-1
if array[left]==target:
return left
if array[right]==target:
return right
return -1
Last Occurrence
和First Occurrence的区别在
1. mid=target时往左还是往右: 右
2. Post-Processing的顺序先后：先检查右边
class Solution(object):
def lastOccur(self, array, target):
"""
input: int[] array, int target
return: int
"""
# write your solution here
if not array or len(array)==0:
return -1
left, right = 0, len(array)-1
while left<right-1:
mid = (left+right)//2
if array[mid]==target:
left = mid
elif array[mid]<target:
left = mid+1
elif array[mid]>target:
right = mid-1
if array[right]==target:
return right
if array[left]==target:
return left
return -1
K Closest to Sorted Array
log(n)+k
line 35其实根本不用abs 因为既然sorted了也就知道谁大谁小了
class Solution(object):
def kClosest(self, array, target, k):
"""
input: int[] array, int target, int k
return: int[]
"""
# write your solution here
res=[]
if len(array)==0 or k==0:
return res
index=self.getIndex(array, target)
l,r=index-1, index+1
res.append(array[index])
while len(res)<k and (l>=0 or r<len(array)):
if r<len(array) and (l<0 or abs(array[l]-target)>abs(array[r]-target)):
res.append(array[r])
r+=1
elif l>=0:
res.append(array[l])
l-=1
return res
def getIndex(self, array, target):
left, right = 0,len(array)-1
while left<right-1:
mid=(left+right)//2
if array[mid]==target:
return mid
elif array[mid]<target:
left=mid
else:
right=mid
return left if abs(array[left]-target)<abs(array[right]-target) else right
class Solution(object):
def kClosest(self, array, target, k):
"""
input: int[] array, int target, int k
return: int[]
"""
# write your solution here
if not array or len(array)==0 or k<0:
return -1
index = self.binarySearch(array, target)
result = []
if k>0:
result.append(array[index])
i,j= index-1, index+1
while len(result)<k and (i>=0 or j<=len(array)-1):
if i>=0 and (j>len(array)-1 or target-array[i]<array[j]-target):
result.append(array[i])
i-=1
else:
result.append(array[j])
j+=1
return result
def binarySearch(self, array, target):
left, right = 0, len(array)-1
while left<right-1:
mid = (left+right)//2
if array[mid]==target:
return mid
elif array[mid]<target:
left = mid
else:
right = mid
return left if (array[right]-target>target-array[left]) else right
1）先append 再移动
2）while循环里if和elif的判断的先后条件，因为很容易list index out of range
还可以这么写 看起来简单点
class Solution(object):
def kClosest(self, array, target, k):
"""
input: int[] array, int target, int k
return: int[]
"""
# write your solution here
if not array or len(array)==0 or k<0:
return -1
index = self.binarySearch(array, target)
l,r=index,index+1
result=[]
for i in range(0,k):
if l>=0 and (r>len(array)-1 or array[r]-target>target-array[l]):
result.append(array[l])
l-=1
else:
result.append(array[r])
r+=1
return result
def binarySearch(self, array, target):
left, right = 0, len(array)-1
while left<right-1:
mid = (left+right)//2
if array[mid]==target:
return mid
elif array[mid]<target:
left = mid
else:
right = mid
return left if (array[right]-target>target-array[left]) else right
int[] findKClosest(int[] array, int target, int K){
int[] res = new int[K];
int closestIdx = findClosest(array, int target);
int l = closestIdx-1;
int r = closestIdx+1;
res[0] = array[closestIdx];
for (i=0, i<K, i++){
if (r>array.length || l>=0 && Math.abs()<Math.abs() ){ //l有可能一上来就是-1 如果一上来k的range已经有了confinement，就不会两边同时出界
}
else{ // r < A.length && l < 0 || Math.abs()
}
}
case1: if input[m]<target('s') -> l=m or l=m+1 both ok
case2: if input[m]==target('e') -> l=m or l=m+1 both ok
case3: if input[m]>target('b') -> r=m 不可以-1
post-processing：先左后右
class Solution(object):
def smallestElementLargerThanTarget(self, array, target):
"""
input: int[] array, int target
return: int
"""
# write your solution here
if not array or len(array)==0:
return -1
left, right = 0, len(array)-1
while left<right-1:
mid=(left+right)//2
if array[mid]==target:
left=mid #+1 OK
elif array[mid]>target:
right=mid #cannot -1
else:
left=mid #+1 OK
if array[left]>target:
return left
elif array[right]>target:
return right
return -1
Sqrt（）
找一个最接近于平方根的整数, floor
方法一：试
def sqrt(n):
val = 1
while val*val<=n
val+=1
return val-1
Time O( (n) )
Space O(1)
方法二：binary search
if mid*mid<n: go right [mid, right]
if mid*mid>n: go left [left, mid]
if mid*mid==n: return mid
class Solution(object):
def sqrt(self, x):
"""
input: int x
return: int
"""
# write your solution here
if x<=1:
return x
left, right = 1, x//2
while left<right-1:
mid = (left+right)//2
if mid*mid==x:
return mid
elif mid*mid>x:
right=mid-1
else:
left=mid
if right*right<=x:
return right
else:
return left
class Solution(object):
def sqrt(self, x):
"""
input: int x
return: int
"""
# write your solution here
if x<=1:
return x
left = 1
right = x//2
while True:
mid = (left+right)//2
if mid>x//mid:
right=mid-1
elif mid<=x//mid and mid+1>x//(mid+1):
return mid
else:
left = mid+1
Find Peak Element
class Solution(object):
def findPeak(self, array):
"""
input: int[] array
return: int
"""
left, right = 0, len(array)-1
while left<right-1:
mid = (left+right)//2
if array[mid]>array[mid-1] and array[mid]>array[mid+1]:
return mid
elif array[mid]<array[mid+1]:
left=mid+1
elif array[mid]>array[mid-1]:
right=mid-1
return left if array[left]>array[right] else right
Search In Shifted Sorted Array I
class Solution(object):
def search(self, array, target):
"""
input: int[] array, int target
return: int
"""
# write your solution here
if not array or len(array)==0:
return -1
left, right = 0, len(array)-1
while left<right-1:
mid=(left+right)//2
if array[mid]==target:
return mid
if array[left]<=array[mid]:
if target<array[mid] and target>=array[left]:
right=mid-1
else:
left=mid+1
else:
if target<=array[right] and target>array[mid]:
left=mid+1
else:
right=mid-1
if array[left]==target:
return left
elif array[right]==target:
return right
return -1
class Solution:
def findFirstBadVersion(n):
# write your solution here
left, right = 1, n
while left<right-1:
mid = (left+right)//2
if isBadVersion(mid):
right=mid
else:
left=mid+1
return left if isBadVersion(left) else right
class Solution extends VersionControl {
public int findFirstBadVersion(int n) {
// write your solution here
while ((n!=1) & (isBadVersion(n))){
n/=2;
}
int left = n;
int right = n*2;
while (left<right-1){
int mid = (right+left)/2;
if (isBadVersion(mid)){
right=mid;
}else{
left=mid+1;
}
}
return isBadVersion(left)? left:right;
}
}
用上面的方法来接着做
1. Binary Search to find L and R log(n)
2. 此时有了两个array，left及left的左边都可以通过当前element和target的距离，这就是所谓的array A，同理，right及right的右边都是arrayB。就成了上面的这个题 log(k)就可以搞定
Search In Unknown Sized Sorted Array
Find the end 倍增法
Binary Search
class Solution(object):
def search(self, dic, target):
"""
input: Dictionary dic, int target
return: int
"""
# write your solution here
start = 1
while dic.get(start) and dic.get(start)<target:
start*=2
left, right = start//2, start
while left<=right:
mid = (left+right)//2
if dic.get(mid) is None or dic.get(mid)>target:
right = mid-1
elif dic.get(mid)<target:
left = mid+1
else:
return mid
return -1
