hw4_lshen.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "57a2163c-f531-446e-ac34-23f349d80c69"
    }
   },
   "source": [
    "## Q1.\n",
    "\n",
    "Use github to integrate our math library from the lab with Travis CI and Coveralls.\n",
    "In the cell below, put a link to your github `cs207test` repo so we can track your badges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "b82a7c83-3cec-4696-b985-3a792939b2a6"
    }
   },
   "source": [
    ">*your answer here*\n",
    "\n",
    "My repo is here.\n",
    "https://github.com/lshen2009/CS207test.git"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f74544f9-98c9-4b5a-837b-a23aa8bda92a"
    }
   },
   "source": [
    "## Q2.\n",
    "\n",
    "Take the implementation of binary search from a previous lecture/lab. Write unit tests for the algorithm (remember we have doctests in there), stripping the doctests down to those that illustrate the interface for a user. How do these doctests deal with the concerns we had?\n",
    "\n",
    "Make sure you have good test coverage. You will be integrationg with Travis and Coveralls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "95aea741-076c-485d-8be1-0a21432d1d2a"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting binsearch.py\n"
     ]
    }
   ],
   "source": [
    "%%file binsearch.py\n",
    "def binary_search(da_array: list, needle, left:int=0, right:int=-1) -> int:\n",
    "    \"\"\"\n",
    "    An algorithm that operates in O(lg(n)) to search for an element\n",
    "    in an array sorted in ascending order.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    da_array : list\n",
    "        a list of \"comparable\"items sorted in non-descending order\n",
    "    needle: an item to find in the array; it may or may not\n",
    "        be in the array\n",
    "    left: int, optional\n",
    "        the left index in the array to search from. Default 0\n",
    "    right: int, optional\n",
    "        the right index in the array to search to. Default is -1\n",
    "        in which case we will use the end of the array `len(da_array) - 1`\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "    index: int\n",
    "        an integer representing the index of `needle` if found, and -1\n",
    "        otherwise\n",
    "        \n",
    "    Notes\n",
    "    -----\n",
    "    PRE: `da_array` is sorted in non-decreasing order (thus items in\n",
    "        `da_array` must be comparable: implement < and ==)\n",
    "    POST: \n",
    "        - `da_array` is not changed by this function (immutable)\n",
    "        - returns `index`=-1 if `needle` is not in `da_array`\n",
    "        - returns an int `index ` in [0:len(da_array)] if\n",
    "          `index` is in `da_array`\n",
    "    INVARIANTS:\n",
    "        - If `needle` in `da_array`, needle in `da_array[rangemin:rangemax]`\n",
    "          is a loop invariant in the while loop below.\n",
    "          \n",
    "    Examples\n",
    "    --------\n",
    "    >>> input = list(range(10))\n",
    "    >>> binary_search(input, 5)\n",
    "    5\n",
    "    >>> binary_search(input, 4.5)\n",
    "    -1\n",
    "    >>> binary_search(input, 10)\n",
    "    -1\n",
    "    >>> binary_search([5], 5)\n",
    "    0\n",
    "    >>> binary_search([5], 4)\n",
    "    -1\n",
    "    >>> import numpy as np\n",
    "    >>> binary_search([1,2,np.inf], 2)\n",
    "    1\n",
    "    >>> binary_search([1,2,np.inf], np.inf)\n",
    "    2\n",
    "    >>> binary_search(input, 5, 1,3)\n",
    "    -1\n",
    "    >>> binary_search(input, 2, 1,3)\n",
    "    2\n",
    "    >>> binary_search(input, 2, 3, 1)\n",
    "    -1\n",
    "    >>> binary_search(input, 2, 2, 2)\n",
    "    2\n",
    "    >>> binary_search(input, 5, 2, 2)\n",
    "    -1\n",
    "    \"\"\"\n",
    "    if left==0:\n",
    "        rangemin = 0\n",
    "    else:\n",
    "        rangemin = left\n",
    "    if right==-1:\n",
    "        rangemax=len(da_array) - 1\n",
    "    else:\n",
    "        rangemax=right\n",
    "    while True:\n",
    "        \"needle in da_array => needle in da_array[rangemin:rangemax]\"   \n",
    "        if rangemin > rangemax:\n",
    "            index = -1\n",
    "            return index\n",
    "        #If rangemin and rangemax are both very high we do not want overflow,\n",
    "        #so get the midpoint like this:\n",
    "        midpoint = rangemin + (rangemax - rangemin)//2\n",
    "        if da_array[midpoint] > needle:#lower part\n",
    "            rangemax = midpoint - 1\n",
    "        elif da_array[midpoint] < needle:\n",
    "            rangemin = midpoint + 1\n",
    "        else:\n",
    "            index = midpoint\n",
    "            return index\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "957438d6-bca9-49e3-a554-8940d76091d3"
    }
   },
   "source": [
    "In addition, we should be **systematic** about testing our code. You should at-least jave some tests like this:\n",
    "\n",
    "1. We should test with wierd data, ie a wierd array: does it have NANs, is it numeric? Does it have 0 elelemts? 1 element? 2?...ie test the boundaries\n",
    "\n",
    "2. Then think of how the needle relates to the above. Try needles less than or greter than the range in the sorted array, besides needles inbetween (in both cases the needle not being in the array). Try needles at the extremes of the array.\n",
    "\n",
    "3. test the integration of 1 and 2 to make sure something has not gone wrong there.\n",
    "\n",
    "Note: you can always compare your answers with linear search implemented in python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "3ec09158-96de-40bf-8452-0f2c9b8f475f"
    }
   },
   "source": [
    "For reference, here are some of our concerns from that lab:\n",
    "\n",
    "#### What's happened to our issue from before?\n",
    "\n",
    "- What if the value is not there in the array? What if it is there multiple times? what are we returning (why the -1). Are we consistent in our returning?\n",
    "\n",
    "We return -1 if the element is not in the array. If it is there multiple times, we will return one of them: it is not defined which. We are consistent by always returning an int, choosing one which cannot be an index.\n",
    "\n",
    "- What if rangemax is so high as to create overflow: \n",
    "\n",
    "We fixed it by using the difference and have documented it in the algorithm\n",
    "\n",
    "\n",
    "- what types are we supporting? . \n",
    "\n",
    "It seems that as long as we have a notion of equals `==`, and a notion of `<` to support sorting we are set. We should document this.\n",
    "\n",
    "- what happens if we have a NaN in our array? Infty?\n",
    "\n",
    "If our preconditions are violated by the user, we can do anything. Doing it nicely might be costly. so we wont.\n",
    "\n",
    "\n",
    "- what if da_array was not an array?\n",
    "\n",
    "The user violated the pre-conditions. Anything could happen. We could check for a list\n",
    "but yhen that would hurt a special class which implemented the python sequence protocol\n",
    "\n",
    "- What happens if array is not sorted: \n",
    "\n",
    "The user violated the pre-conditions. We could return an error, violate post conditions. If we sort it we'd violate the o(lg(n)) notion. (fixing it seems dubious). Can we check if its sorted? This is naively O(n) and breaks our performance specifications. We can create a guard to terminate the array at more than n iterations for the infinite case or let the user have enough rope to hang themselves\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "5eea1575-209b-44b6-bd42-671deffca17f"
    }
   },
   "source": [
    "**Submit** this to us by creating a repo `cs207binsearch` under your userid with a file `binarysearch.py` and accompanying test file(s). Intergrate with Travis CI and Coveralls. Set up badges on the README of your repo. Write the link to your repo below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "aecf710d-aeb9-4fb3-a9a5-a7c7e6206f49"
    }
   },
   "source": [
    ">*your answer here*\n",
    "\n",
    "https://github.com/lshen2009/cs207binsearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "3c7dee81-0dbe-4d53-8941-3e0abbeefaa7"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting binsearch.py\n"
     ]
    }
   ],
   "source": [
    "%%file binsearch.py\n",
    "def binary_search(da_array: list, needle, left:int=0, right:int=-1) -> int:       \n",
    "    \"\"\"\n",
    "    An algorithm that operates in O(lg(n)) to search for an element\n",
    "    in an array sorted in ascending order.\n",
    "    \n",
    "    Newly added documentation by Lu Shen, Sep 29, 2016\n",
    "    ----------\n",
    "    Warning: We strongly suggest the user to avoid the below situations, which\n",
    "    will voilate the O(log(n)) time complexity. \n",
    "    (1) It is not incrementally sorted.\n",
    "    (2) It contains missing data or non-numeric elements.\n",
    "\n",
    "    We report an error if the needle is outside the range of da_array.  \n",
    "    -----------\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    da_array : list\n",
    "        a list of \"comparable\"items sorted in non-descending order\n",
    "    needle: an item to find in the array; it may or may not\n",
    "        be in the array\n",
    "    left: int, optional\n",
    "        the left index in the array to search from. Default 0\n",
    "    right: int, optional\n",
    "        the right index in the array to search to. Default is -1\n",
    "        in which case we will use the end of the array `len(da_array) - 1`\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "    index: int\n",
    "        an integer representing the index of `needle` if found, and -1\n",
    "        otherwise\n",
    "        \n",
    "    Notes\n",
    "    -----\n",
    "    PRE: `da_array` is sorted in non-decreasing order (thus items in\n",
    "        `da_array` must be comparable: implement < and ==)\n",
    "    POST: \n",
    "        - `da_array` is not changed by this function (immutable)\n",
    "        - returns `index`=-1 if `needle` is not in `da_array`\n",
    "        - returns an int `index ` in [0:len(da_array)] if\n",
    "          `index` is in `da_array`\n",
    "    INVARIANTS:\n",
    "        - If `needle` in `da_array`, needle in `da_array[rangemin:rangemax]`\n",
    "          is a loop invariant in the while loop below.\n",
    "          \n",
    "    Examples\n",
    "    --------\n",
    "    >>> input = list(range(10))\n",
    "    >>> binary_search(input, 5)\n",
    "    5\n",
    "    >>> binary_search(input, 4.5)\n",
    "    -1\n",
    "    >>> binary_search(input, 10) #We report an error in this test exercise here, Lu Shen, Sep 29\n",
    "    -1\n",
    "    >>> binary_search([5], 5)\n",
    "    0\n",
    "    >>> binary_search([5], 4)\n",
    "    -1\n",
    "    >>> import numpy as np\n",
    "    >>> binary_search([1,2,np.inf], 2)\n",
    "    1\n",
    "    >>> binary_search([1,2,np.inf], np.inf)\n",
    "    2\n",
    "    >>> binary_search(input, 5, 1,3)\n",
    "    -1\n",
    "    >>> binary_search(input, 2, 1,3)\n",
    "    2\n",
    "    >>> binary_search(input, 2, 3, 1)\n",
    "    -1\n",
    "    >>> binary_search(input, 2, 2, 2)\n",
    "    2\n",
    "    >>> binary_search(input, 5, 2, 2)\n",
    "    -1\n",
    "    \"\"\"    \n",
    "    import numpy as np    \n",
    "    #----- The test clodes are here, Lu Shen, Sep 29 -----\n",
    "    if type(da_array) not in (tuple,list):\n",
    "        raise TypeError(\"The array is not a list or tuple\")        \n",
    "    n=len(da_array)\n",
    "    if n==0:\n",
    "        raise ValueError(\"can't search in a list with length being 0\")  \n",
    "    else:        \n",
    "        if not all(isinstance(x,(int,float)) for x in da_array):            \n",
    "            raise TypeError(\"Not all elements are integers\")          \n",
    "        if np.isnan(da_array).any():\n",
    "            raise ValueError(\"This array has missing data\")            \n",
    "        if n>=2:          \n",
    "            if any(da_array[i] > da_array[i+1] for i in range(len(da_array)-1)):        \n",
    "                raise TypeError(\"Not sorted\")\n",
    "            if needle<min(da_array) or needle>max(da_array):\n",
    "                raise ValueError(\"The needle is outside the range of the array\")    \n",
    "    #------end of the test codes ----------------------------\n",
    "    \n",
    "    if left==0:\n",
    "        rangemin = 0\n",
    "    else:\n",
    "        rangemin = left\n",
    "    if right==-1:\n",
    "        rangemax=len(da_array) - 1\n",
    "    else:\n",
    "        rangemax=right\n",
    "    while True:\n",
    "        \"needle in da_array => needle in da_array[rangemin:rangemax]\"   \n",
    "        if rangemin > rangemax:\n",
    "            index = -1\n",
    "            return index\n",
    "        #If rangemin and rangemax are both very high we do not want overflow,\n",
    "        #so get the midpoint like this:\n",
    "        midpoint = rangemin + (rangemax - rangemin)//2\n",
    "        if da_array[midpoint] > needle:#lower part\n",
    "            rangemax = midpoint - 1\n",
    "        elif da_array[midpoint] < needle:\n",
    "            rangemin = midpoint + 1\n",
    "        else:\n",
    "            index = midpoint\n",
    "            return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "871c3ff3-3f7b-4f5c-97fb-e43c7fcbe064"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting test_binsearch.py\n"
     ]
    }
   ],
   "source": [
    "%%file test_binsearch.py\n",
    "from pytest import raises\n",
    "from binsearch import binary_search\n",
    "import numpy as np\n",
    "\n",
    "def test_mymath():\n",
    "    input = list(range(10))\n",
    "    assert binary_search(input,5) == 5\n",
    "    assert binary_search(input,4.5) == -1\n",
    "    assert binary_search([5],5) == 0\n",
    "    assert binary_search(input, 5, 1,3) == -1\n",
    "    assert binary_search(input, 2, 1,3) == 2\n",
    "    assert binary_search(input, 2, 3, 1) == -1\n",
    "    assert binary_search(input, 2, 2, 2) == 2\n",
    "    assert binary_search(input, 5, 2, 2) == -1    \n",
    "def test_infinite_data():    \n",
    "    assert binary_search([1,2,np.inf], 2) == 1\n",
    "    assert binary_search([1,2,np.inf], np.inf) == 2\n",
    "def test_array_type():\n",
    "    with raises(TypeError):\n",
    "        binary_search(5,5)\n",
    "def test_missing_data():#The time complexity is O(n), so I add one warning in the doc    \n",
    "    with raises(ValueError):\n",
    "        binary_search([1,2,3,4,np.nan],2)  \n",
    "def test_zero_elements():\n",
    "    with raises(ValueError):\n",
    "        binary_search([],2)  \n",
    "def test_non_int_elements():\n",
    "    with raises(TypeError):\n",
    "        binary_search(['a',2,3],2)\n",
    "def test_sorted():#The time complexity is O(n), so I add one warning in the doc\n",
    "    with raises(TypeError):\n",
    "        binary_search([4,2,3],2)         \n",
    "def test_needle_toolarge():# In this case, we assume that it returns an error if the needle is too large\n",
    "    with raises(ValueError):\n",
    "        binary_search([1,2,3,4],5) \n",
    "def test_needle_toosmall():# In this case, we assume that it returns an error if the needle is too small\n",
    "    with raises(ValueError):\n",
    "        binary_search([1,2,3,4],-2)  \n",
    "def test_missing_and_str():#An integration of two errors together    \n",
    "    with raises(TypeError):\n",
    "        binary_search([1,2,3,4,\"a\",np.nan],2)          \n",
    "def test_missing_and_str_large_needle():#An integration of three errors together    \n",
    "    with raises(TypeError):\n",
    "        binary_search([1,2,3,4,\"a\",np.nan],5)                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "4cd0db9d-83d2-45a3-ba48-a74888b766ed"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[1m============================= test session starts ==============================\u001b[0m\n",
      "platform darwin -- Python 3.5.2, pytest-2.9.2, py-1.4.31, pluggy-0.3.1\n",
      "rootdir: /Users/lulushen/Desktop/CS207/cs207work, inifile: \n",
      "plugins: cov-2.3.1\n",
      "collected 11 items \n",
      "\u001b[0m\n",
      "test_binsearch.py ...........\n",
      "\n",
      "---------- coverage: platform darwin, python 3.5.2-final-0 -----------\n",
      "Name                Stmts   Miss  Cover   Missing\n",
      "-------------------------------------------------\n",
      "binsearch.py           33      0   100%\n",
      "test_binsearch.py      43      0   100%\n",
      "-------------------------------------------------\n",
      "TOTAL                  76      0   100%\n",
      "\n",
      "\n",
      "\u001b[32m\u001b[1m========================== 11 passed in 0.37 seconds ===========================\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "!py.test  --cov --cov-report term-missing binsearch.py test_binsearch.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "4eae65bd-bdc8-4b62-92a8-761c4895d6d8"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cloning into '/tmp/cs207binsearch'...\n",
      "remote: Counting objects: 20, done.\u001b[K\n",
      "remote: Compressing objects: 100% (14/14), done.\u001b[K\n",
      "remote: Total 20 (delta 6), reused 15 (delta 4), pack-reused 0\u001b[K\n",
      "Unpacking objects: 100% (20/20), done.\n",
      "Checking connectivity... done.\n"
     ]
    }
   ],
   "source": [
    "!rm -rf /tmp/cs207binsearch\n",
    "!git clone https://github.com/lshen2009/cs207binsearch.git /tmp/cs207binsearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true,
    "nbpresent": {
     "id": "3bcffa27-5ac9-4ed2-865d-d17317591c4d"
    }
   },
   "outputs": [],
   "source": [
    "!cp binsearch.py test_binsearch.py /tmp/cs207binsearch/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "6f588da1-f78b-4db6-9027-850c8686b2f5"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting /tmp/cs207binsearch/setup.cfg\n"
     ]
    }
   ],
   "source": [
    "%%file /tmp/cs207binsearch/setup.cfg\n",
    "[pytest]\n",
    "addopts =  --cov-report term-missing --cov test_binsearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "b28ee694-5da5-46fa-acb0-e3a6cfb7c07a"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting /tmp/cs207binsearch/.travis.yml\n"
     ]
    }
   ],
   "source": [
    "%%file /tmp/cs207binsearch/.travis.yml\n",
    "language: python\n",
    "python:\n",
    "    - \"3.5\"\n",
    "before_install:\n",
    "    - pip install pytest pytest-cov\n",
    "script:\n",
    "    - py.test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "595c1391-43d9-4241-97e4-9cd47176cd5c"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/tmp/cs207binsearch ~/Desktop/CS207/cs207work\n",
      "[master 4044468] travis integration\n",
      " 2 files changed, 11 insertions(+), 8 deletions(-)\n",
      "~/Desktop/CS207/cs207work\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "To https://github.com/lshen2009/cs207binsearch.git\n",
      "   6984c3f..4044468  master -> master\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "pushd /tmp/cs207binsearch\n",
    "git add .\n",
    "git commit -m \"travis integration\" -a\n",
    "git push\n",
    "popd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "4b83b7b3-32c2-44cc-af4e-93c267dbeff1"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting /tmp/cs207binsearch/.travis.yml\n"
     ]
    }
   ],
   "source": [
    "%%file /tmp/cs207binsearch/.travis.yml\n",
    "language: python\n",
    "python:\n",
    "    - \"3.5\"\n",
    "before_install:\n",
    "    - pip install pytest pytest-cov\n",
    "    - pip install coveralls\n",
    "script:\n",
    "    - py.test\n",
    "after_success:\n",
    "    - coveralls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "e296a102-56ba-4392-b0a7-878bb526ebd8"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/tmp/cs207binsearch ~/Desktop/CS207/cs207work\n",
      "[master 207b2ac] added coveralls\n",
      " 1 file changed, 4 insertions(+), 1 deletion(-)\n",
      "~/Desktop/CS207/cs207work\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "To https://github.com/lshen2009/cs207binsearch.git\n",
      "   4044468..207b2ac  master -> master\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "pushd /tmp/cs207binsearch\n",
    "git add .\n",
    "git commit -m \"added coveralls\" -a\n",
    "git push\n",
    "popd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "af691f35-7283-43c0-8fe5-33e72a30876d"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting /tmp/cs207binsearch/README.md\n"
     ]
    }
   ],
   "source": [
    "%%file /tmp/cs207binsearch/README.md\n",
    "\n",
    "# cs207binsearch\n",
    "\n",
    "[![Build Status](https://travis-ci.org/lshen2009/cs207binsearch.svg?branch=master)](https://travis-ci.org/lshen2009/cs207binsearch)\n",
    "\n",
    "[![Coverage Status](https://coveralls.io/repos/github/lshen2009/cs207binsearch/badge.svg?branch=master)](https://coveralls.io/github/lshen2009/cs207binsearch?branch=master)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "c60698e7-3524-4158-82d1-c480b4322748"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/tmp/cs207binsearch ~/Desktop/CS207/cs207work\n",
      "On branch master\n",
      "Your branch is up-to-date with 'origin/master'.\n",
      "nothing to commit, working tree clean\n",
      "~/Desktop/CS207/cs207work\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Everything up-to-date\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "pushd /tmp/cs207binsearch\n",
    "git add .\n",
    "git commit -m \"added badges\" -a\n",
    "git push\n",
    "popd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbpresent": {
     "id": "bf2a9374-948a-400c-94aa-36703333f02a"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbpresent": {
     "id": "39a37abf-37aa-4d7f-a8f3-8986d51802dc"
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  },
  "nbpresent": {
   "slides": {
    "055fc067-6b2d-432f-8baa-2b8329a204ae": {
     "id": "055fc067-6b2d-432f-8baa-2b8329a204ae",
     "prev": "f6923452-bd77-49f3-aa2c-c2fc44afb1ff",
     "regions": {
      "21183c44-a446-4450-b560-82e6a9278c6f": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "5eea1575-209b-44b6-bd42-671deffca17f",
        "part": "whole"
       },
       "id": "21183c44-a446-4450-b560-82e6a9278c6f"
      }
     }
    },
    "2e18ad89-ec3f-46f3-8d7d-f73cbf7e45bc": {
     "id": "2e18ad89-ec3f-46f3-8d7d-f73cbf7e45bc",
     "prev": "b69b2841-97ed-448c-9065-f91f721b45e8",
     "regions": {
      "3218ebab-58b1-4a67-90a8-eb575e87cb05": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4b83b7b3-32c2-44cc-af4e-93c267dbeff1",
        "part": "whole"
       },
       "id": "3218ebab-58b1-4a67-90a8-eb575e87cb05"
      }
     }
    },
    "49db3366-6827-4195-869c-33fefc12c7ce": {
     "id": "49db3366-6827-4195-869c-33fefc12c7ce",
     "prev": "a6e35868-7609-43f5-9cfb-2182a96ed63b",
     "regions": {
      "1205a44c-48e6-4462-b8f4-cd290f605f74": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "957438d6-bca9-49e3-a554-8940d76091d3",
        "part": "whole"
       },
       "id": "1205a44c-48e6-4462-b8f4-cd290f605f74"
      }
     }
    },
    "5ae91a6d-24f4-45af-8d41-2491233197a6": {
     "id": "5ae91a6d-24f4-45af-8d41-2491233197a6",
     "prev": "2e18ad89-ec3f-46f3-8d7d-f73cbf7e45bc",
     "regions": {
      "48c1bde1-6fa6-4233-a335-c4f192893229": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "e296a102-56ba-4392-b0a7-878bb526ebd8",
        "part": "whole"
       },
       "id": "48c1bde1-6fa6-4233-a335-c4f192893229"
      }
     }
    },
    "5ff8a79b-1644-447e-acc4-1c8202f8f1f8": {
     "id": "5ff8a79b-1644-447e-acc4-1c8202f8f1f8",
     "prev": "e966925f-8763-41de-b27e-bb9167ea6288",
     "regions": {
      "a2b297a7-0fc7-4088-b004-49e4931c2ad1": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "f74544f9-98c9-4b5a-837b-a23aa8bda92a",
        "part": "whole"
       },
       "id": "a2b297a7-0fc7-4088-b004-49e4931c2ad1"
      }
     }
    },
    "61057c1e-3ce7-4b91-8494-dc2bb1ba0157": {
     "id": "61057c1e-3ce7-4b91-8494-dc2bb1ba0157",
     "prev": null,
     "regions": {
      "f302a5b6-5be0-4d2d-8f16-dd1fc96a6f77": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "57a2163c-f531-446e-ac34-23f349d80c69",
        "part": "whole"
       },
       "id": "f302a5b6-5be0-4d2d-8f16-dd1fc96a6f77"
      }
     }
    },
    "8c781780-a9f2-4613-b27a-55f844f66ba6": {
     "id": "8c781780-a9f2-4613-b27a-55f844f66ba6",
     "prev": "abbebe8e-a549-48b6-ae3c-932951c68c24",
     "regions": {
      "2b270ba9-a5db-4d99-8bfa-dedb2213c744": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "b28ee694-5da5-46fa-acb0-e3a6cfb7c07a",
        "part": "whole"
       },
       "id": "2b270ba9-a5db-4d99-8bfa-dedb2213c744"
      }
     }
    },
    "a6e35868-7609-43f5-9cfb-2182a96ed63b": {
     "id": "a6e35868-7609-43f5-9cfb-2182a96ed63b",
     "prev": "5ff8a79b-1644-447e-acc4-1c8202f8f1f8",
     "regions": {
      "b37b8f74-7515-40d4-99d4-dc5cf759b902": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "95aea741-076c-485d-8be1-0a21432d1d2a",
        "part": "whole"
       },
       "id": "b37b8f74-7515-40d4-99d4-dc5cf759b902"
      }
     }
    },
    "a820b540-873b-40e0-b4f9-68caeb2ffb35": {
     "id": "a820b540-873b-40e0-b4f9-68caeb2ffb35",
     "prev": "055fc067-6b2d-432f-8baa-2b8329a204ae",
     "regions": {
      "67106f8f-0b66-406d-ad2b-852214679e69": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "aecf710d-aeb9-4fb3-a9a5-a7c7e6206f49",
        "part": "whole"
       },
       "id": "67106f8f-0b66-406d-ad2b-852214679e69"
      }
     }
    },
    "ab72f06d-c61c-4b88-8fd9-0776b32312e9": {
     "id": "ab72f06d-c61c-4b88-8fd9-0776b32312e9",
     "prev": "db0dda90-14df-4e17-a631-a2a0c2cd3da6",
     "regions": {
      "fcfb83f0-e798-42b1-9441-f700ab30e6bd": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "c60698e7-3524-4158-82d1-c480b4322748",
        "part": "whole"
       },
       "id": "fcfb83f0-e798-42b1-9441-f700ab30e6bd"
      }
     }
    },
    "abbebe8e-a549-48b6-ae3c-932951c68c24": {
     "id": "abbebe8e-a549-48b6-ae3c-932951c68c24",
     "prev": "d585a6dd-0f7b-435c-9cf5-06d8a63213dc",
     "regions": {
      "db0b0fe9-aad3-4b6b-bc1a-1ba4c6ca7d4b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "6f588da1-f78b-4db6-9027-850c8686b2f5",
        "part": "whole"
       },
       "id": "db0b0fe9-aad3-4b6b-bc1a-1ba4c6ca7d4b"
      }
     }
    },
    "b21ef270-ce22-4bec-8aa5-970349910d54": {
     "id": "b21ef270-ce22-4bec-8aa5-970349910d54",
     "prev": "b93952f7-2e07-4ddc-9685-e64b2534ddad",
     "regions": {
      "1baf98b7-f78e-4a6d-94e3-d9896414ba81": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "39a37abf-37aa-4d7f-a8f3-8986d51802dc",
        "part": "whole"
       },
       "id": "1baf98b7-f78e-4a6d-94e3-d9896414ba81"
      }
     }
    },
    "b69b2841-97ed-448c-9065-f91f721b45e8": {
     "id": "b69b2841-97ed-448c-9065-f91f721b45e8",
     "prev": "8c781780-a9f2-4613-b27a-55f844f66ba6",
     "regions": {
      "a93d892e-4630-42d3-b310-c404b3770742": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "595c1391-43d9-4241-97e4-9cd47176cd5c",
        "part": "whole"
       },
       "id": "a93d892e-4630-42d3-b310-c404b3770742"
      }
     }
    },
    "b93952f7-2e07-4ddc-9685-e64b2534ddad": {
     "id": "b93952f7-2e07-4ddc-9685-e64b2534ddad",
     "prev": "ab72f06d-c61c-4b88-8fd9-0776b32312e9",
     "regions": {
      "07418fb4-7cb0-451b-b432-80514a307549": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "bf2a9374-948a-400c-94aa-36703333f02a",
        "part": "whole"
       },
       "id": "07418fb4-7cb0-451b-b432-80514a307549"
      }
     }
    },
    "c2129dd8-9b07-455a-af2d-c59718a0c3e8": {
     "id": "c2129dd8-9b07-455a-af2d-c59718a0c3e8",
     "prev": "caf43c51-6ecb-444a-b3af-da002b8cfb9c",
     "regions": {
      "002b1479-d154-475e-ab3e-a15cf1e69aff": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4eae65bd-bdc8-4b62-92a8-761c4895d6d8",
        "part": "whole"
       },
       "id": "002b1479-d154-475e-ab3e-a15cf1e69aff"
      }
     }
    },
    "caf43c51-6ecb-444a-b3af-da002b8cfb9c": {
     "id": "caf43c51-6ecb-444a-b3af-da002b8cfb9c",
     "prev": "f02c72c6-b46b-414a-9dd5-d255a5611cf3",
     "regions": {
      "f5fc3e27-9bfd-4d2a-94f6-fb37a5fc4d94": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4cd0db9d-83d2-45a3-ba48-a74888b766ed",
        "part": "whole"
       },
       "id": "f5fc3e27-9bfd-4d2a-94f6-fb37a5fc4d94"
      }
     }
    },
    "cf64632f-2df4-4026-bca9-0d9b5b35d09a": {
     "id": "cf64632f-2df4-4026-bca9-0d9b5b35d09a",
     "prev": "a820b540-873b-40e0-b4f9-68caeb2ffb35",
     "regions": {
      "932ab327-2777-4fbd-8079-6d322018213f": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "3c7dee81-0dbe-4d53-8941-3e0abbeefaa7",
        "part": "whole"
       },
       "id": "932ab327-2777-4fbd-8079-6d322018213f"
      }
     }
    },
    "d585a6dd-0f7b-435c-9cf5-06d8a63213dc": {
     "id": "d585a6dd-0f7b-435c-9cf5-06d8a63213dc",
     "prev": "c2129dd8-9b07-455a-af2d-c59718a0c3e8",
     "regions": {
      "a3f25713-c118-467d-aeeb-784af015cc00": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "3bcffa27-5ac9-4ed2-865d-d17317591c4d",
        "part": "whole"
       },
       "id": "a3f25713-c118-467d-aeeb-784af015cc00"
      }
     }
    },
    "db0dda90-14df-4e17-a631-a2a0c2cd3da6": {
     "id": "db0dda90-14df-4e17-a631-a2a0c2cd3da6",
     "prev": "5ae91a6d-24f4-45af-8d41-2491233197a6",
     "regions": {
      "58479433-dc0f-4765-87ce-849e6d84ebbb": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "af691f35-7283-43c0-8fe5-33e72a30876d",
        "part": "whole"
       },
       "id": "58479433-dc0f-4765-87ce-849e6d84ebbb"
      }
     }
    },
    "e966925f-8763-41de-b27e-bb9167ea6288": {
     "id": "e966925f-8763-41de-b27e-bb9167ea6288",
     "prev": "61057c1e-3ce7-4b91-8494-dc2bb1ba0157",
     "regions": {
      "5e279a91-4d8e-4aef-b14f-961831a16e1f": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "b82a7c83-3cec-4696-b985-3a792939b2a6",
        "part": "whole"
       },
       "id": "5e279a91-4d8e-4aef-b14f-961831a16e1f"
      }
     }
    },
    "f02c72c6-b46b-414a-9dd5-d255a5611cf3": {
     "id": "f02c72c6-b46b-414a-9dd5-d255a5611cf3",
     "prev": "cf64632f-2df4-4026-bca9-0d9b5b35d09a",
     "regions": {
      "6666c39c-1474-4fef-8c7d-dba424a5ef41": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "871c3ff3-3f7b-4f5c-97fb-e43c7fcbe064",
        "part": "whole"
       },
       "id": "6666c39c-1474-4fef-8c7d-dba424a5ef41"
      }
     }
    },
    "f6923452-bd77-49f3-aa2c-c2fc44afb1ff": {
     "id": "f6923452-bd77-49f3-aa2c-c2fc44afb1ff",
     "prev": "49db3366-6827-4195-869c-33fefc12c7ce",
     "regions": {
      "7d76b313-016d-42f5-86df-a976aa2d517d": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "3ec09158-96de-40bf-8452-0f2c9b8f475f",
        "part": "whole"
       },
       "id": "7d76b313-016d-42f5-86df-a976aa2d517d"
      }
     }
    }
   },
   "themes": {}
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}