2 Finding values in collections Todo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "random.seed(1000)\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Create Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# number of elements in list\n",
    "n = 50\n",
    "\n",
    "# list of unsorted items\n",
    "items = [int(random.random()*n) for _ in range(n)]\n",
    "\n",
    "# value to be searched in list\n",
    "value = int(random.random()*n)\n",
    "\n",
    "# sorted list \n",
    "sorted_items = sorted(items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Find Value in Unsorted List with Linear Search\n",
    "\n",
    "Animation: https://yongdanielliang.github.io/animation/web/LinearSearchNew.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_item(items, index):\n",
    "    \"\"\"value of of an item in a list based on the index of the value\n",
    "        args:\n",
    "            - items: List of items\n",
    "            - index: index of the requested item\n",
    "        return:\n",
    "            - value of the requested item\n",
    "    \"\"\"\n",
    "    if index == -1:\n",
    "        print(\"Not in the list\")\n",
    "        return None\n",
    "    else:\n",
    "        return items[index] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_element(items, value):\n",
    "    \"\"\"Linear search for a value in a list of items\n",
    "        args:\n",
    "            - items: unsorted list of items\n",
    "            - value: searched value\n",
    "        return:\n",
    "            - index of value or -1 if not in list\n",
    "    \"\"\"\n",
    "    # TODO\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "index = find_element(items, value)\n",
    "print(index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(value)\n",
    "get_item(items, index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question: \n",
    "* Time your function with differently sized inputs by\n",
    "* searching for each input size for a non-existing element\n",
    "* and plot the change of the time to the size of the input\n",
    "\n",
    "(see 1 Timing Algorithms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question: What is the time complexity of searching for a value in an unsorted list?\n",
    "\n",
    "Big O Notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO: Your answer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Find Value in Sorted list with Binary Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Animation: https://yongdanielliang.github.io/animation/web/BinarySearchNew.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_sorted(items, value):\n",
    "    \"\"\"Bineary search for a value in a list of sorted items\n",
    "        args:\n",
    "            - items: sorted list of items\n",
    "            - value: searched value\n",
    "        return:\n",
    "            - index of value or -1 if not in list\n",
    "    \"\"\"\n",
    "    # TODO\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a value that is not in the list so that we get the worst case time\n",
    "value = n+1 \n",
    "find_sorted(sorted_items, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 100\n",
    "items = [int(random.random()*n) for _ in range(n)]\n",
    "value = n+1 \n",
    "find_sorted(sorted_items, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 200\n",
    "items = [int(random.random()*n) for _ in range(n)]\n",
    "value = n+1 \n",
    "find_sorted(sorted_items, value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question: \n",
    "* Time your function with differently sized inputs by\n",
    "* searching for each input size for a non-existing element\n",
    "* and plot the change of the time to the size of the input\n",
    "\n",
    "(see 1 Timing Algorithms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question: What is the time complexity of binary search? \n",
    "\n",
    "Big O Notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO: Your answer"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.12"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "oldHeight": 123.2,
   "position": {
    "height": "40px",
    "left": "1012.5px",
    "right": "20px",
    "top": "120px",
    "width": "250px"
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "varInspector_section_display": "none",
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}