Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 21, 2018 18:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/e85d4fc864049fe553235aba7a16027e to your computer and use it in GitHub Desktop.
Save jianminchen/e85d4fc864049fe553235aba7a16027e to your computer and use it in GitHub Desktop.
binary search - code review written by python - two arrays with size m and n, m>>n, how to find the duplicate elements?
##arr1 = [2, 3], arr2 = [3, 6, 7]
def bst_search(arr,value): #[3,6,7] , 2
left = 0 # 0,
right = len(arr) - 1 # 2
while(right >= left): # True, True, False
mid = left + (right-left)//2 # 1, 0,
if arr[mid] == value: #False, False
return value
if value > arr[mid]: # False, False
left = mid + 1
else: # right = 0, right = -1
right = mid - 1
return None
def find_duplicates(arr1, arr2):
output = [] # duplicate
# swap the array to put smaller one first
for i in range(0, len(arr1)): # 2,
search = arr1[i]
if bst_search(arr2,search) == search: # 0
output.append(search)
return output
arr1 = [1, 2, 3, 5, 6, 7]
arr2 = [3, 6, 7, 8, 20]
print(find_duplicates(arr1,arr2))
"""
# arr1 = [1, 2, 3, 5, 6, 7]
# arr2 = [3, 6, 7, 8, 20]
output = [3,6,7]
len(arr2)>>len(arr1)>0
point1, point2
1,2,3,5,6,7
^p1
3, 6, 7, 8, 20
^p2
for p1 in range(0,len(arr2)):
p2 = 0
while(arr1[p2]<arr2[p1])
m = 10
n = 1,000, 000
what is time complexity? m * logn -> m << n
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment