add search insert algorithm

dori-dev · dori-dev · commit 2ef04d4d1628 · 2022-08-02T11:39:20.000+04:30
diff --git a/arrays/search_insert.py b/arrays/search_insert.py
@@ -0,0 +1,61 @@
+"""
+search_insert([1, 3, 5, 6], 3) => 1
+search_insert([1, 3, 5, 6], 4) => 2
+search_insert([1, 3, 5, 6], 7) => 4
+search_insert([1, 3, 5, 6], 0) => 0
+"""
+
+from typing import Any
+
+
+def bubble_sort(array: list) -> list:
+    array = array.copy()
+    length = len(array)
+    for i in range(length - 1):
+        swapped = False
+        for j in range(length - i-1):
+            if array[j] > array[j+1]:
+                swapped = True
+                array[j], array[j+1] = array[j+1], array[j]
+        if not swapped:
+            break
+    return array
+
+
+def get_index(array: list, element: Any) -> int:
+    index = 0
+    for item in array:
+        if item == element:
+            return index
+        index += 1
+    return None
+
+
+def get_insert_place(array: list, target: int) -> int:
+    low = 0
+    hight = len(array) - 1
+    while low <= hight:
+        middle = (low + hight) // 2
+        if array[middle] < target:
+            low = middle + 1
+        else:
+            hight = middle - 1
+    return low
+
+
+def search_insert(array: list, number: int) -> int:
+    # complexity: O(n^2)
+    bubble_sort(array)
+    # complexity: O(n)
+    index = get_index(array, number)
+    if index is None:
+        # complexity: O(log n)
+        return get_insert_place(array, number)
+    return index
+
+
+if __name__ == "__main__":
+    print(search_insert([1, 3, 5, 6], 3) == 1)
+    print(search_insert([1, 3, 5, 6], 4) == 2)
+    print(search_insert([1, 3, 5, 6], 7) == 4)
+    print(search_insert([1, 3, 5, 6], 0) == 0)
