Binary_Search_Examination.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Binary Search!\n",
        "\n",
        "Using Python I am going to break down the Binary Search Algorithm using two approaches: Loop Iteration and Recursion. Binary Search is an algorithm that was designed as an efficient way to search for an object in a sorted set, often referred to as an array in coding. According to research the concept behind the Binary Search algorithm has been around for hundreds of years. The Jataka collections, which were written between 300 BC and 400 AD, described it similar to the recursion method.\n",
        "\n",
        "  \n",
        "\n",
        "> \"So in time it came to pass that the people fell into a wretched plight. Reflecting that such had not been their lot in former days, but that now they were going to rack and ruin, they concluded that there must be some breeder of misfortune among them, and resolved to divide into two bands. This they did; and there were then two bands of five hundred families each. Thence-forward, ruin dogged the band which included the parents of the future Losaka, whilst the other five hundred families throve apace. So the former resolved to go on halving their numbers, and did so, until this one family was parted from all the rest.\"\n",
        "\n",
        "https://sites.pitt.edu/~dash/jataka.html\n",
        "https://sacred-texts.com/bud/j1/j1044.html\n",
        "\n",
        "Binary Search is the computer form of that logic, divide and conquer! Essentially, if we know the elements of a list are arranged in a certain way, then we can quicken the time it takes to search by taking a comparrison of what we are looking for and the middle of a list. This allows us to decide where to search next - either in the left half or the right half of the list. We can then keep doing this until we find our mark!\n",
        "\n",
        "Why use this over a normal linear search?\n",
        "Well... say we have a list of numbers from 1 to 1,000,000. If we have to start from 1 and we are looking for 1,000,000 then we have to search every single element of this list. With Divide and Conquer, we are constantly skipping a head huge chunks of the array.\n",
        "\n",
        "Now when we talk about how long it takes for the algorithm to run, thats where we really see the advantages. While a standard linear search has a worst case running time of Θ(n) complexity to locate an element, Binary Search optimizes this to Θ(logn). (If Time Complexity is new to you, please read this: https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/)\n",
        "\n",
        "\n",
        "For further reading on the algorithm and it's discovery I recommend:\n",
        "The Art of Computer Programming, Vol 3, second edition.\n"
      ],
      "metadata": {
        "id": "58fhFjpwD85B"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Psuedocode:\n",
        "\n",
        "Below I'll begin with breakinng down our goal in Psuedocode. This is a way of basically laying down a blueprint for your algorithm using normal language so as to be able to layer your logic correctly.\n",
        "\n",
        "```\n",
        "Binary Search Algorithm\n",
        "\n",
        "1. Start with an array that is sorted.\n",
        "2. Initialize two pointers: 'left' at the start of the array, and 'right' at the end.\n",
        "3. While 'left' pointer is not greater than 'right' pointer:\n",
        "   a. Find the middle element of the array. This is at index ('left' + 'right') / 2.\n",
        "   b. Compare the middle element with the target value.\n",
        "   c. If they are equal, return the index of the middle element.\n",
        "   d. If the target value is less than the middle element, move the 'right' pointer\n",
        "      to the middle - 1 (search the left half).\n",
        "   e. If the target value is greater than the middle element, move the 'left' pointer\n",
        "      to the middle + 1 (search the right half).\n",
        "4. If the target value is not found, return that it is not in the array.\n",
        "\n",
        "```\n",
        "\n",
        "\n",
        "\n",
        "Now we will put this into practice! We can do this two ways, both are equally effective in their own rights, whichever you chose to implement is up to you and your needs / preferences.\n",
        "\n"
      ],
      "metadata": {
        "id": "49dSOyv9kJRT"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Recursion Method"
      ],
      "metadata": {
        "id": "MSd1sYwkokfb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# First we will create our recursion algorithm that will be called later on\n",
        "def binarySearcher(inputList, elmt, left, right):\n",
        "    # Ensure our search area is not empty\n",
        "    if (left > right):\n",
        "      return None\n",
        "    else:\n",
        "      # extract mid\n",
        "      mid = (left + right) // 2\n",
        "      # Check to see if we have a match\n",
        "      if (elmt == inputList[mid]):\n",
        "        # if so, return our index\n",
        "        return mid\n",
        "      # If less, recall function with the left half\n",
        "      elif (elmt < inputList[mid]):\n",
        "        return binarySearcher(inputList, elmt, left, mid - 1)\n",
        "      # If more, recall function with the right half\n",
        "      else:\n",
        "        return binarySearcher(inputList, elmt, mid + 1, right)"
      ],
      "metadata": {
        "id": "J1BWlwyOokFp"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "n1ADzU6HD3wg"
      },
      "outputs": [],
      "source": [
        "def binarySearchRec(inputList, elmt):\n",
        "    # Ensure the list is sorted by checking the list against pythons sorted version\n",
        "    # NOTE: This is here only to ensure these showcased algorithms function under any test cases.\n",
        "    # Sorting inside the algorithm takes theta(n) run time and would be ideally handled outside of this algorithm normally\n",
        "    if (sorted(inputList) != inputList):\n",
        "      return None\n",
        "    # Then create a safeguard against empty lists\n",
        "    elif (len(inputList) < 1):\n",
        "      return None\n",
        "    # Now we double check to be sure the object we are searching for is within the range of our set\n",
        "    else:\n",
        "      if (elmt < inputList[0] or elmt > inputList[(len(inputList)-1)]):\n",
        "        return None\n",
        "      # Checks complete, all our searcher\n",
        "      else:\n",
        "        return binarySearcher(inputList, elmt, 0, (len(inputList)-1))\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Test 1: Empty List\n",
        "print(\"searching for 5 in an empty list\")\n",
        "assert binarySearchRec([], 5) is None, \"Fail: Empty List\"\n",
        "print(\"1 Good!\")\n",
        "\n",
        "# Test 2: Single Element\n",
        "print(\"searching for a single element\")\n",
        "assert binarySearchRec([5], 5) == 0, \"Fail: Single Element\"\n",
        "print(\"2 Good!\")\n",
        "\n",
        "# Test 3: Multiple Elements\n",
        "print(\"searching for 7 in [1, 3, 5, 7, 9]\")\n",
        "test_list = [1, 3, 5, 7, 9]\n",
        "assert binarySearchRec(test_list, 7) == 3, \"Fail: Multiple Elements\"\n",
        "print(\"3 Good!\")\n",
        "\n",
        "# Test 4: Element Not in List\n",
        "print(\"searching for an element not present in array\")\n",
        "assert binarySearchRec(test_list, 4) is None, \"Fail: Element Not in List\"\n",
        "print(\"4 Good!\")\n",
        "\n",
        "# Test 5: First and Last Element\n",
        "print(\"searching for book-end elements\")\n",
        "assert binarySearchRec(test_list, 1) == 0, \"Fail: First Element\"\n",
        "assert binarySearchRec(test_list, 9) == 4, \"Fail: Last Element\"\n",
        "print(\"5 Good!\")\n",
        "\n",
        "# Test 6: Negative Numbers\n",
        "print(\"searching for negative element\")\n",
        "negative_list = [-5, -3, -1, 1, 3]\n",
        "assert binarySearchRec(negative_list, -3) == 1, \"Fail: Negative Numbers\"\n",
        "print(\"6 Good!\")\n",
        "\n",
        "# Test 7: Unsorted List\n",
        "print(\"Testing an un-sorted list\")\n",
        "unsorted_list = [3, 1, 4, 2]\n",
        "assert binarySearchRec(unsorted_list, 2) is None, \"Fail: Unsorted List\"\n",
        "print(\"7 Good!\")\n",
        "\n",
        "# Test 8: Boundary Conditions\n",
        "print(\"searching for quantitative boundaries\")\n",
        "assert binarySearchRec(test_list, 1) == 0, \"Fail: Smallest Element\"\n",
        "assert binarySearchRec(test_list, 9) == 4, \"Fail: Largest Element\"\n",
        "print(\"8 Good!\")\n",
        "\n",
        "# Test 9: Duplicate Elements\n",
        "print(\"searching for duplicate elements\")\n",
        "duplicate_list = [1, 2, 2, 3, 4]\n",
        "assert binarySearchRec(duplicate_list, 2) in [1, 2], \"Fail: Duplicate Elements\"\n",
        "print(\"All complete\")\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Y7-7LQlc_GOV",
        "outputId": "e75371f2-c182-4b51-8719-52fe71272570"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "searching for 5 in an empty list\n",
            "1 Good!\n",
            "searching for a single element\n",
            "2 Good!\n",
            "searching for 7 in [1, 3, 5, 7, 9]\n",
            "3 Good!\n",
            "searching for an element not present in array\n",
            "4 Good!\n",
            "searching for book-end elements\n",
            "5 Good!\n",
            "searching for negative element\n",
            "6 Good!\n",
            "Testing an un-sorted list\n",
            "7 Good!\n",
            "searching for quantitative boundaries\n",
            "8 Good!\n",
            "searching for duplicate elements\n",
            "All complete\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Looping Method"
      ],
      "metadata": {
        "id": "YVyWDdi4WE7N"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def binarySearchLoop (listInput, elmt):\n",
        "  # Once again check for sorting\n",
        "  # NOTE: This is here only to ensure these showcased algorithms function under any test cases.\n",
        "  # Sorting inside the algorithm takes theta(n) run time and would be ideally handled outside of this algorithm normally\n",
        "  if (sorted(listInput) != listInput):\n",
        "    return None\n",
        "  # Check for empty lists\n",
        "  elif (len(listInput) < 1):\n",
        "    return None\n",
        "  else:\n",
        "    # Establish our L & R\n",
        "    left = 0\n",
        "    right = (len(listInput)) - 1\n",
        "    while left <= right:\n",
        "      # extract mid\n",
        "      mid = (left + right) // 2\n",
        "      # Perform our comparrisons\n",
        "      if mid == listInput[elmt]:\n",
        "        return mid\n",
        "      elif elmt < listInput[mid]:\n",
        "        right = mid - 1\n",
        "      else:\n",
        "        left = mid + 1\n",
        "  # Return None if elmnt not found\n",
        "  return None"
      ],
      "metadata": {
        "id": "ow09InViWKz3"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Test 1: Empty List\n",
        "print(\"searching inside an empty list\")\n",
        "assert binarySearchLoop([], 5) is None, \"Fail: Empty List\"\n",
        "print(\"1 Good!\")\n",
        "\n",
        "# Test 2: Single Element\n",
        "print(\"searching for an element in a size 1 list\")\n",
        "assert binarySearchLoop([5], 5) == 0, \"Fail: Single Element\"\n",
        "print(\"2 Good!\")\n",
        "\n",
        "# Test 3: Multiple Elements\n",
        "test_list = [1, 3, 5, 7, 9]\n",
        "print(\"standard search\")\n",
        "assert binarySearchLoop(test_list, 7) == 3, \"Fail: Multiple Elements\"\n",
        "print(\"3 Good!\")\n",
        "\n",
        "# Test 4: Element Not in List\n",
        "print(\"searching for an element not inside list\")\n",
        "assert binarySearchLoop(test_list, 4) is None, \"Fail: Element Not in List\"\n",
        "print(\"4 Good!\")\n",
        "\n",
        "# Test 5: First and Last Element\n",
        "print(\"searching for 'book end' elements\")\n",
        "assert binarySearchLoop(test_list, 1) == 0, \"Fail: First Element\"\n",
        "assert binarySearchLoop(test_list, 9) == 4, \"Fail: Last Element\"\n",
        "print(\"5 Good!\")\n",
        "\n",
        "# Test 6: Negative Numbers\n",
        "negative_list = [-5, -3, -1, 1, 3]\n",
        "print(\"searching for negatives\")\n",
        "assert binarySearchLoop(negative_list, -3) == 1, \"Fail: Negative Numbers\"\n",
        "print(\"6 Good!\")\n",
        "\n",
        "# Test 7: Unsorted List\n",
        "unsorted_list = [3, 1, 4, 2]\n",
        "print(\"proof against unsorted lists\")\n",
        "assert binarySearchLoop(unsorted_list, 2) is None, \"Fail: Unsorted List\"\n",
        "print(\"7 Good!\")\n",
        "\n",
        "# Test 8: Boundary Conditions\n",
        "print(\"searching for quantitative boundaries\")\n",
        "assert binarySearchLoop(test_list, 1) == 0, \"Fail: Smallest Element\"\n",
        "assert binarySearchLoop(test_list, 9) == 4, \"Fail: Largest Element\"\n",
        "print(\"8 Good!\")\n",
        "\n",
        "# Test 9: Duplicate Elements\n",
        "duplicate_list = [1, 2, 2, 3, 4]\n",
        "print(\"searching for elements in lists with duplicates\")\n",
        "assert binarySearchLoop(duplicate_list, 2) in [1, 2], \"Fail: Duplicate Elements\"\n",
        "print(\"9 Good!\")\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ajgjwv--nt-P",
        "outputId": "de2a8a7a-c31e-4b5b-9be9-96e2e6171915"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Searching for 9 in list [0,2,3,4,6,9,12]\n",
            "6\n",
            "Searching for 8 in list [1, 3, 4, 6, 8, 9,10, 11, 12, 15]\n",
            "5\n",
            "Searching for 5 in list [1, 3, 4, 6, 8, 9,10, 11, 12, 15]\n",
            "3\n",
            "Searching for 0 in list [0,2]\n",
            "0\n",
            "Searching for 1 in list [0,2]\n",
            "1\n",
            "Searching for 2 in list [0,2]\n",
            "1\n"
          ]
        }
      ]
    }
  ]
}