#-------------------------------------------------------------------------------
# Name: Search Insert Position
# Purpose:
#
# 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.
# Here are few examples.
# [1,3,5,6], 5 --> 2
# [1,3,5,6], 2 --> 1
# [1,3,5,6], 7 --> 4
# [1,3,5,6], 0 --> 0
#-------------------------------------------------------------------------------
def searchInsert(A, target):
return searchInsertRecur(A, target, 0, len(A) - 1)
def searchInsertRecur(A, target, low, high):
mid = (high + low) / 2
if low > high:
return low
if A[mid] == target:
return mid
if A[mid] < target:
return searchInsertRecur(A, target, mid + 1, high)
return searchInsertRecur(A, target, low, mid - 1)
def binary_search(A, target):
lo = 0
hi = len(A) - 1
while lo <= hi:
mid = (lo + hi) / 2
if A[mid] == target:
return mid
if A[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return lo
#-------------------------------------------------------------------------------
# Name: Search in Rotated Sorted Array
# Purpose:
#
# Suppose a sorted array 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.
#-------------------------------------------------------------------------------
def search(A, target):
return _search(A, target, len(A) - 1, 0)
def _search(A, target, hi, lo):
if hi < lo:
return -1
mid = (hi + lo) / 2
if A[mid] == target:
return mid
cdn1 = (A[0] < A[mid] and target < A[mid] and target >= A[0])
cdn2 = (A[mid] < A[hi] and (target < A[mid] or target > A[hi]))
if cdn1 or cdn2:
return _search(A, target, mid - 1, lo)
return _search(A, target, hi, mid + 1)
a = [ 4, 5, 6, 7, 0, 1, 2]
print search(a, 7)
#-------------------------------------------------------------------------------
# Name: Search a 2D Matrix
# Purpose:
#
# 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.
#-------------------------------------------------------------------------------
def searchMatrix(matrix, target):
collen, rowlen = len(matrix[0]), len(matrix)
if 0 in [rowlen, collen]:
return False
lo, hi = 0, rowlen*collen - 1
x, y, mid = 0, 0, 0
while lo <= hi:
mid = (lo + hi) / 2;
x = mid / collen
y = mid % collen
if matrix[x][y] == target:
return True
elif target < matrix[x][y]:
hi = mid - 1
else:
lo = mid + 1
return False
a = [
[1, 3, 5, 6], [10, 11, 16, 20], [23, 30, 34, 50]
]
print searchMatrix(a, 7)
#-------------------------------------------------------------------------------
# Name: Merge Sorted Array
# Purpose:
#
# Given two sorted integer arrays A and B, merge B into A as one sorted array.
# Note:
# You may assume that A has enough space (size that is greater or
# equal to m + n) to hold additional elements from B. The number
# of elements initialized in A and B are mand n respectively.
#-------------------------------------------------------------------------------
import unittest
class BufferError(Exception):
pass
def merge(A, B):
if not isinstance(A, list) or not isinstance(B, list):
raise ValueError, 'A or B must be valid lists'
sizeBuffer = sum(a is None for a in A)
n = len(B)
if sizeBuffer < n:
raise BufferError, 'not enough buffer'
_merge(A, len(A)-sizeBuffer, B, n)
return A
def _merge(A, m, B, n):
last = m + n - 1
i = m - 1
j = n - 1
while i >= 0 and j >= 0:
if A[i] > B[j]:
A[last] = A[i]
i -= 1
else:
A[last] = B[j]
j -= 1
last -= 1
while j >= 0:
A[last] = B[j]
j -= 1
last -= 1
class MyTest(unittest.TestCase):
def test_merge_functional(self):
self.assertEqual(merge([1, 3, 5, None, None], [2, 4]), [1, 2, 3, 4, 5])
self.assertEqual(merge([1, 3, 100, None, None], [2, 4]), [1, 2, 3, 4, 100])
@unittest.expectedFailure
def test_merge_nonfunctional(self):
"""not working for not sorted array"""
self.assertEqual(merge([1, 9, 5, None, None], [2, 4]), [1, 2, 4, 5, 9])
self.assertEqual(merge([1, 3, 5, None, None], [4, 2]), [1, 2, 3, 4, 5])
def test_merge_exception(self):
self.assertRaises(BufferError, merge, [1, 3, 5], [2, 4])
self.assertRaises(ValueError, merge, 1, [2, 4])
if __name__ == "__main__":
unittest.main()#-------------------------------------------------------------------------------
# Name: Find Minimum in Rotated Sorted Array
# Purpose:
# Suppose a sorted array 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).
# Find the minimum element.
# You may assume no duplicate exists in the array.
#-------------------------------------------------------------------------------
def findMin(num):
lo, hi = 0, len(num) - 1
while lo <= hi:
if num[lo] <= num[hi]:
return num[lo]
mid = (lo + hi) / 2
if num[mid] < num[hi]:
hi = mid
else:
lo = mid + 1
print findMin([0])
print findMin([4, 5, 6, 7, 8, 0, 1, 2])
print findMin([4, 5, 6, 7, 0, 1, 2])
print findMin([4, 5, 6, 7, 8, 9, 0, 1, 2])
print findMin([7, 0, 1, 2, 3, 4, 5, 6])
print findMin([7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6])