코딩테스트
Algorithms
로그앤
2023. 6. 22. 12:14
1. BINARY SEARCH
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2 # Calculate the middle index
if arr[mid] == target:
return mid # Found the target, return its index
elif arr[mid] < target:
low = mid + 1 # Target is in the right half
else:
high = mid - 1 # Target is in the left half
return -1 # Target was not found
# Example usage:
my_list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target_number = 12
result = binary_search(my_list, target_number)
if result != -1:
print("Element found at index", result)
else:
print("Element not found in the list.")2. TWO PONITER
def two_pointer(arr, target):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [arr[left], arr[right]]
elif current_sum < target:
left += 1
else:
right -= 1
return []
# Example usage:
my_list = [1, 3, 5, 7, 9, 11]
target_sum = 10
result = two_pointer(my_list, target_sum)
if result:
print("Pair found:", result)
else:
print("No pair found.")3. SLIDING WINDOW
def sliding_window(arr, k):
window_sum = sum(arr[:k]) # Calculate the initial window sum
max_sum = window_sum # Initialize the maximum sum as the initial window sum
for i in range(k, len(arr)):
window_sum = window_sum - arr[i - k] + arr[i] # Update the window sum
if window_sum > max_sum:
max_sum = window_sum
return max_sum
# Example usage:
my_list = [4, 2, 1, 7, 8, 1, 2, 8, 1, 0]
window_size = 3
max_sum = sliding_window(my_list, window_size)
print("Maximum sum within a window of size", window_size, ":", max_sum)4. BRUTE FORCE
def brute_force(arr, target):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == target:
return [arr[i], arr[j]]
return []
# Example usage:
my_list = [2, 4, 6, 8, 10]
target_sum = 14
result = brute_force(my_list, target_sum)
if result:
print("Pair found:", result)
else:
print("No pair found.")