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].
解：两次binary search, 先左边界，nums[mid]<target, 后右边界，nums[mid]<= target
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1, -1]
left, right = 0, 0
start, end = 0, len(nums)-1
while start + 1 < end:
mid = start + (end -start)/2
if nums[mid] < target:
start = mid
else:
end = mid
if nums[start] == target:
left = start
elif nums[end] == target:
left = end
else:
left = -1
start, end = 0, len(nums)-1
while start + 1 < end:
mid = start + (end - start)/2
if nums[mid] <= target:
start = mid
else:
end = mid
if nums[end] == target:
right = end
elif nums[start] == target:
right = start
else:
right = -1
return [left, right]
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
"""
if not nums:
return -1
start, end = 0, len(nums)-1
while start + 1 < end:
mid = start + (end - start)/2
if nums[mid] == target:
return mid
elif nums[start] < nums[mid]:
if target >= nums[start] and target <= nums[mid]:
end = mid
else:
start = mid
elif nums[mid] < nums[end]:
if target <= nums[end] and target >= nums[mid]:
start = mid
else:
end = mid
if nums[end] == target:
return end
elif nums[start] == target:
return start
else:
return -1
Sqrt(x)
" def sqrt(self, x):
# write your code here
if x <= 1:
return x
start, end = 0, x
while start + 1 < end:
mid = start + (end - start)/2
if mid * mid == x:
return mid
elif mid * mid < x:
start = mid
else:
end = mid
if end * end <= x:
return end
return start"
Guess Number Game
"class Solution:
# @param {int} n an integer
# @return {int} the number you guess
def guessNumber(self, n):
# Write your code here
start, end = 1, n
while start+1 < end:
mid = start + (end-start)/2
if Guess.guess(mid) == 0: return mid
elif Guess.guess(mid) == 1: start = mid
elif Guess.guess(mid) == -1: end = mid
if Guess.guess(start) == 0: return start
elif Guess.guess(end) == 0: return end
else:
return -1"
Closest Number in Sorted Array
" def closestNumber(self, A, target):
# Write your code here
if not A:
return -1
start, end = 0, len(A)-1
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] == target:
return mid
elif A[mid] < target:
start = mid
else:
end = mid
if A[end] - target > target - A[start]:
return start
else:
return end"
Last Position of Target
" def lastPosition(self, A, target):
# Write your code here
if not A or target is None:
return -1
start, end = 0, len(A)-1
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] == target:
start = mid
elif A[mid] < target:
start = mid
else:
end = mid
if A[end] == target:
return end
elif A[start] == target:
return start
else:
return -1"
Search a 2D Matrix
" def searchMatrix(self, matrix, target):
# write your code here
if not matrix or target is None:
return False
n, m = len(matrix), len(matrix[0])
start, end = 0, n * m -1
while start + 1 < end:
mid = start + (end - start) / 2
x, y = mid / m, mid % m
if matrix[x][y] < target:
start = mid
else:
end = mid
x, y = start / m, start % m
if matrix[x][y] == target:
return True
x, y = end / m, end % m
if matrix[x][y] == target:
return True
return False"
Maximum Number in Mountain Sequence
" def mountainSequence(self, nums):
# Write your code here
if not nums:
return -1
start, end = 0, len(nums)-1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] < nums[mid+1]:
start = mid
else:
end = mid
return max(nums[start], nums[end])"
Search in a Big Sorted Array
" def searchBigSortedArray(self, reader, target):
# write your code here
index = 0
while reader.get(index) < target:
index = 2 * index + 1
start, end = 0, index
while start + 1 < end:
mid = start + (end - start) / 2
if reader.get(mid) >= target:
end = mid
else:
start = mid
if reader.get(start) == target:
return start
if reader.get(end) == target:
return end
return -1"
Find Minimum in Rotated Sorted Array
" def findMin(self, nums):
# write your code here
if not nums:
return -1
start, end = 0, len(nums)-1
target = nums[-1]
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] <= target:
end = mid
else:
start = mid
return min(nums[start], nums[end])"
Find Peak Element
" def findPeak(self, A):
# write your code here
if not A:
return -1
start, end = 0, len(A)-1
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] < A[mid-1]:
end = mid
elif A[mid] < A[mid+1]:
start = mid
else:
end = mid
if A[start] < A[end]:
return end
else:
return start"
First Bad Version
" def findFirstBadVersion(self, n):
# write your code here
if not n:
return -1
start, end = 1, n
while start + 1 < end:
mid = start + (end - start) / 2
if SVNRepo.isBadVersion(mid):
end = mid
else:
start = mid
if SVNRepo.isBadVersion(start):
return start
return end"
Smallest Rectangle Enclosing Black Pixels
"class Solution(object):
# @param image {List[List[str]]} a binary matrix with '0' and '1'
# @param x, y {int} the location of one of the black pixels
# @return an integer
def minArea(self, image, x, y):
# Write your code here
m = len(image)
if m == 0:
return 0
n = len(image[0])
if n == 0:
return 0
start, end = y, n-1
while start < end:
mid = start + (end - start)/2 + 1
if self.checkColumn(image, mid):
start = mid
else:
end = mid - 1
right = start
start, end = 0, y
while start < end:
mid = start + (end - start)/2
if self.checkColumn(image, mid):
end = mid
else:
start = mid + 1
left = start
start, end = x, m - 1
while start < end:
mid = start + (end - start)/2 + 1
if self.checkRow(image, mid):
start = mid
else:
end = mid -1
down = start
start, end = 0, x
while start < end:
mid = start + (end - start)/2
if self.checkRow(image, mid):
end = mid
else:
start = mid + 1
up = start
return (right - left + 1) * (down - up + 1)
def checkColumn(self, image, col):
for i in xrange(len(image)):
if image[i][col] == '1':
return True
return False
def checkRow(self, image, row):
for i in xrange(len(image[0])):
if image[row][i] == '1':
return True
return False"
Total Occurrence of Target
"def totalOccurrence(self, A, target):
# Write your code here
if not A:
return 0
count = 0
start, end = 0, len(A)-1
while start + 1 < end:
mid = start + (end - start)/2
if A[mid] < target:
start = mid
else:
end = mid
if A[start] == target:
head = start
elif A[end] == target:
head = end
else:
head = -1
start, end = 0, len(A)-1
while start + 1 < end:
mid = start + (end - start)/2
if A[mid] <= target:
start = mid
else:
end = mid
if A[end] == target:
tail = end
elif A[start] == target:
tail = start
else:
tail = -1
if tail >= 0 and head >= 0:
return (tail - head + 1)
else:
return 0"
Drop Eggs
" def dropEggs(self, n):
# Write your code here
import math
x = int(math.sqrt(n * 2))
while x*(x+1) / 2 < n:
x += 1
return x"
Divide Two Integers
" def divide(self, dividend, divisor):
# Write your code here
MAX_INT = 2147483647
if divisor == 0:
return MAX_INT
neg = dividend > 0 and divisor < 0 or dividend < 0 and divisor > 0
a, b = abs(dividend), abs(divisor)
ans, shift = 0, 31
while shift >= 0:
if a >= b<<shift:
a -= b<<shift
ans += 1<<shift
shift -= 1
if neg:
ans = -ans
if ans > MAX_INT:
return MAX_INT
return ans"
Search a 2D Matrix II
" def searchMatrix(self, matrix, target):
# write your code here
row = len(matrix)
if row == 0:
return 0
col = len(matrix[0])
if col == 0:
return 0
count = 0
i, j = row-1, 0
while i>=0 and j < col:
if matrix[i][j] == target:
count += 1
i -= 1
j +=1
elif matrix[i][j] > target:
i -= 1
elif matrix[i][j] < target:
j += 1
return count"
Sqrt(x) II
" def sqrt(self, x):
# Write your code here
left = 0.0
right = x
eps = 1e-12
if x < 1.0:
right = 1.0
while (right - left > eps):
mid = (right + left)/2
if mid * mid < x:
left = mid
else:
right = mid
return left"
First Position of Target
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):
# write your code here
if not nums:
return -1
left, right = 0, len(nums)-1
while left + 1 < right:
mid = left + (right - left)/2
if nums[mid] < target:
left = mid
elif nums[mid] >= target:
right = mid
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1