Skip to content

Instantly share code, notes, and snippets.

@wmwong
Last active December 23, 2015 16:29
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save wmwong/6662429 to your computer and use it in GitHub Desktop.
# Iterative by number of iterations.
def chop(target, array)
found = false
start_index = 0
end_index = array.size - 1
check_index = 0
# Find the max iterations to perform.
# log2(0) is infinity so we have a special case for it.
# After log2(), we +1 because we still need to check the last value. floor()
# is used instead of ceil() because of the +1.
iterations = array.size == 0 ? 0 : (Math.log2(array.size) + 1).floor
iterations.times do
# Find the middle index between start and end.
# Using floor() instead of ceil() because array indices start from 0 and
# floor() gives middle or round up automatically.
# Remember to add back on the start_index.
check_index = ((end_index - start_index) / 2).floor + start_index
check = array[check_index]
# 3 parts
# - middle
# - lower
# - upper
if target == check
found = true
break
elsif target < check
end_index = check_index - 1
else
start_index = check_index + 1
end
end
# If found, return the index. Else return -1 for not found.
found ? check_index : -1
end
# Recursive by slicing array.
def chop(target, array)
# Stop condition. If the array is empty, return -1 for not found.
return -1 if array.empty?
# Find the middle index.
# Using floor() instead of ceil() because array indices start from 0 and
# floor() gives middle or round up automatically.
check_index = (array.size / 2).floor
check = array[check_index]
# 3 parts
# - middle
# - lower
# - upper
if target == check
check_index
elsif target < check
# Perform a binary search in the lower part.
chop(target, array.slice(0, check_index))
else
# Perform a binary search in the upper part.
index = chop(target, array.slice(check_index + 1, array.size - check_index))
# If not found, continue to propogate.
return index if index == -1
# If found, add back on the index.
index + check_index + 1
end
end
# Iterative by while.
def chop(target, array)
found = false
start_index = 0
end_index = array.size - 1
check_index = 0
# Continue binary search until found or the start index is larger than the
# end index.
while !found && start_index <= end_index
# Find the middle index between start and end.
# Using floor() instead of ceil() because array indices start from 0 and
# floor() gives middle or round up automatically.
# Remember to add back on the start_index.
check_index = ((end_index - start_index) / 2).floor + start_index
check = array[check_index]
# 3 parts
# - middle
# - lower
# - upper
if target == check
found = true
elsif target < check
end_index = check_index - 1
else
start_index = check_index + 1
end
end
# If found, return the index. Else return -1 for not found.
found ? check_index : -1
end
# Recursive by keeping the array.
def chop(target, array, options = {})
# Set the defaults if not passed in.
start_index = options[:start_index] || 0
end_index = options[:end_index] || array.size - 1
# Stop condition. If the array is empty, return -1 for not found.
return -1 if start_index > end_index
# Find the middle index between start and end.
# Using floor() instead of ceil() because array indices start from 0 and
# floor() gives middle or round up automatically.
# Remember to add back on the start_index.
check_index = ((end_index - start_index) / 2).floor + start_index
check = array[check_index]
# 3 parts
# - middle
# - lower
# - upper
if target == check
check_index
elsif target < check
chop(target, array, start_index: start_index, end_index: check_index - 1)
else
chop(target, array, start_index: check_index + 1, end_index: end_index)
end
end
# Threads.
def chop(target, array, options = {})
found_index = -1
# Create the lambda to do the checking.
chop_thread = lambda do |options = {}|
# Set the defaults if not passed in.
start_index = options[:start_index] || 0
end_index = options[:end_index] || array.size - 1
# Stop condition. If the array is empty, stop.
return if start_index > end_index
# Find the middle index between start and end.
# Using floor() instead of ceil() because array indices start from 0 and
# floor() gives middle or round up automatically.
# Remember to add back on the start_index.
check_index = ((end_index - start_index) / 2).floor + start_index
check = array[check_index]
# 3 parts
# - middle
# - lower
# - upper
if target == check
# Update the found_index.
found_index = check_index
elsif target < check
Thread.new { chop_thread.call(start_index: start_index, end_index: check_index - 1) }.join
else
Thread.new { chop_thread.call(start_index: check_index + 1, end_index: end_index) }.join
end
end
# Kick off the threading.
Thread.new { chop_thread.call }.join
# Return the index.
found_index
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment