This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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