Two Sum Problem Solution

two_sum.py

from typing import List

class Solution:
    def binary_search(self, container: List[int], key):
        low = 0
        high = len(container) - 1
        while (low <= high):
            middle = (low + high) >> 1
            middle_value = container[middle]
            if middle_value < key:
                low = middle + 1
            elif middle_value > key:
                high = middle - 1
            else:
                return middle
        return None
    
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Binary Search solution
        for index, value in enumerate(nums):
            complement = target - value
            complement_index = self.binary_search(nums, complement)
            if complement_index is not None:
                if complement_index != index:
                    return [index, complement_index]
        return None

    def two_sum_hash_table(self, nums: List[int], target: int) -> List[int]:
        table = dict()
        for index, value in enumerate(nums):
            complement = target - value
            if value not in table:
                table[complement] = index
            else:
                return [index, table[value]]
        return []