Repository: eeshannarula29/structlinks (language: python)

Issue:
Searching algorithms 
add Searching algorithms library



Discussion / hints:

Fix patch:
diff --git a/.gitignore b/.gitignore
index 8870495..5b9b629 100644
--- a/.gitignore
+++ b/.gitignore
@@ -4,3 +4,4 @@
 \__pycache__
 \.idea
 .DS_Store
+conftest.py
\ No newline at end of file
diff --git a/SearchingAlgorithms.py b/SearchingAlgorithms.py
new file mode 100644
index 0000000..c4f1f38
--- /dev/null
+++ b/SearchingAlgorithms.py
@@ -0,0 +1,50 @@
+"""
+A re-implementation of several searching algorithms, including:
+    - Binary Search
+
+Many of these sort are inspired by their implementations in the CSC111
+University of Toronto Course.
+"""
+
+from typing import Any
+
+
+def linear_search(lst: list, item: Any) -> bool:
+    """Return a boolean representing whether or not the given item
+    exists in the list.
+    """
+    # Iterate through all items in the list
+    for i in lst:
+        if item == i:  # If the target item is found
+            return True
+
+    # If we reach this point, the item is not in the list
+    return False
+
+
+def binary_search(lst: list, item: Any) -> bool:
+    """Return a boolean representing whether or not the given item
+    exists in the list.
+
+    Preconditions:
+        - lst must be sorted
+    """
+    # Initialize our upper and lower bounds of the search area
+    b = 0
+    e = len(lst)
+
+    # We will have verified the entire list when b >= e
+    while b < e:
+        # Get the middle index
+        m = (e + b) // 2
+
+        # Check if the middle item is the target
+        if lst[m] == item:
+            return True
+        elif lst[m] < item:
+            e = m
+        else:
+            b = m + 1
+
+    # If we reach this point, the item is not in the list
+    return False
diff --git a/SortingAlgorithms.py b/SortingAlgorithms.py
index 6e939a4..77a24fc 100644
--- a/SortingAlgorithms.py
+++ b/SortingAlgorithms.py
@@ -5,8 +5,8 @@
     - Selection sort
     - Insertion sort
 
-Many of these sort are inspired by the implementation of the CSC111
-University of Toronto Course
+Many of these sort are inspired by their implementations in the CSC111
+University of Toronto Course.
 
 Implementation Notes:
     - Non-mutating algorithms are explicitely prefixed with no_mut_


Test patch:
diff --git a/tests/test_DoublyLinkedList.py b/tests/test_DoublyLinkedList.py
index a778093..90e5859 100644
--- a/tests/test_DoublyLinkedList.py
+++ b/tests/test_DoublyLinkedList.py
@@ -1,9 +1,5 @@
 """The file contains unit tests for  Doubly linked list class"""
 
-# Add the root directory to PYTHONPATH
-import sys
-sys.path.append('.')
-
 from DoublyLinkedList import DoublyLinkedList
 
 
diff --git a/tests/test_LinkedList.py b/tests/test_LinkedList.py
index fdb56ce..b1c915c 100644
--- a/tests/test_LinkedList.py
+++ b/tests/test_LinkedList.py
@@ -1,9 +1,5 @@
 """The file contains unit tests for linked list class"""
 
-# Add the root directory to PYTHONPATH
-import sys
-sys.path.append('.')
-
 from LinkedList import LinkedList
 
 
diff --git a/tests/test_Queue.py b/tests/test_Queue.py
index 358dfc8..a71b765 100644
--- a/tests/test_Queue.py
+++ b/tests/test_Queue.py
@@ -2,10 +2,6 @@
 
 from Queue import *
 
-# Add the root directory to PYTHONPATH
-import sys
-sys.path.append('.')
-
 
 class TestQueue:
 
diff --git a/tests/test_SearchingAlgorithms.py b/tests/test_SearchingAlgorithms.py
new file mode 100644
index 0000000..c7d2410
--- /dev/null
+++ b/tests/test_SearchingAlgorithms.py
@@ -0,0 +1,84 @@
+"""This file contains tests for SortingAlgorithms.py.
+"""
+from typing import Optional, Callable, Any
+
+from SearchingAlgorithms import *
+
+
+########################################
+# Base tests for searching algorithms
+########################################
+class BaseSearch:
+    """The base class for the series of tests that
+    evaluate the efficacy of searching functions.
+    """
+    algorithm: Callable[[list, Any], bool] = staticmethod(None)
+
+    def test_sorted_list_first_true(self) -> None:
+        """Test the searching algorithm on a sorted list
+        for the item at the first index."""
+        lst = [0, 1, 2, 3, 4, 5, 6, 7, 8]
+
+        assert self.algorithm(lst, 0)
+
+    def test_sorted_list_middle_true(self) -> None:
+        """Test the searching algorithm on a sorted list.
+        for the item at the middle index."""
+        lst = [0, 1, 2, 3, 4, 5, 6, 7, 8]
+
+        assert self.algorithm(lst, 5)
+
+    def test_sorted_list_last_true(self) -> None:
+        """Test the searching algorithm on a sorted list.
+        for the item at the last index."""
+        lst = [0, 1, 2, 3, 4, 5, 6, 7, 8]
+
+        assert self.algorithm(lst, 8)
+
+    def test_sorted_list_false(self) -> None:
+        """Test the searching algorithm on a sorted list
+        for an item not in the list."""
+        lst = [0, 1, 2, 3, 4, 5, 6, 7, 8]
+
+        assert not self.algorithm(lst, 4.5)
+
+    def test_sorted_list_odd_length(self) -> None:
+        """Test the searching algorithm on a sorted list of odd length."""
+        lst = [0, 1, 2, 3, 4, 5, 6, 7, 8]
+
+        assert self.algorithm(lst, 7)
+
+    def test_sorted_list_even_length(self) -> None:
+        """Test the searching algorithm on a sorted list of even length."""
+        lst = [0, 1, 2, 3, 4, 5, 6, 7]
+
+        assert self.algorithm(lst, 7)
+
+    def test_empty_list(self) -> None:
+        """Test the searching algorithm on an empty list."""
+        lst = []
+
+        assert not self.algorithm(lst, 7)
+
+
+class TestLinearSearch(BaseSearch):
+    """Test the mutating selection sort algorithm"""
+    algorithm: Optional[tuple[Callable[[list], None]]] = staticmethod(linear_search)
+
+    def test_unsorted_list_odd_length(self) -> None:
+        """Test the searching algorithm on an unsorted list
+        of odd length."""
+        lst = [2, 3, 1, 2, 7, 3, 4]
+
+        assert self.algorithm(lst, 7)
+
+    def test_unsorted_list_even_length(self) -> None:
+        """Test the searching algorithm on an unsorted list
+        of even length."""
+        lst = [2, 3, 1, 2, 7, 9, 8, 5, 3, 4]
+
+        assert self.algorithm(lst, 7)
+
+class TestBinarySearch(BaseSearch):
+    """Test the mutating selection sort algorithm"""
+    algorithm: Optional[tuple[Callable[[list], None]]] = staticmethod(linear_search)
\ No newline at end of file
diff --git a/tests/test_SortingAlgorithms.py b/tests/test_SortingAlgorithms.py
index fba9aaf..8cd82fc 100644
--- a/tests/test_SortingAlgorithms.py
+++ b/tests/test_SortingAlgorithms.py
@@ -1,8 +1,4 @@
 """This file contains tests for SortingAlgorithms.py.
-
-Because it exists in a /tests/ folder, it adds the
-current working directory to PYTHONPATH, in order to 'see'
-the functions it is testing
 """
 from SortingAlgorithms import *
 from LinkedList import *
@@ -10,11 +6,6 @@
 
 from typing import Optional, Callable
 
-# Add the root directory to PYTHONPATH
-import sys
-
-sys.path.append('.')
-
 
 ########################################
 # Base tests for non-mutating sorts
diff --git a/tests/test_Stack.py b/tests/test_Stack.py
index 5541993..eff995b 100644
--- a/tests/test_Stack.py
+++ b/tests/test_Stack.py
@@ -4,11 +4,6 @@
 
 from Stack import *
 
-# Add the root directory to PYTHONPATH
-import sys
-
-sys.path.append('.')
-
 
 class TestStack: