{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bisect import bisect_left, bisect_right # for binary search\n",
    "import random\n",
    "random.seed(77) # so that you and I get same random lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 5)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1, 2, 3, 3, 3, 4, 5]\n",
    "bisect_left(a, 3), bisect_right(a, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 2)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [2, 4, 6, 8, 10]\n",
    "bisect_left(a, 5), bisect_right(a, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[80,\n",
       " 33,\n",
       " 24,\n",
       " 82,\n",
       " 12,\n",
       " 48,\n",
       " 56,\n",
       " 61,\n",
       " 15,\n",
       " 63,\n",
       " 50,\n",
       " 85,\n",
       " 3,\n",
       " 95,\n",
       " 18,\n",
       " 81,\n",
       " 51,\n",
       " 83,\n",
       " 19,\n",
       " 32,\n",
       " 9,\n",
       " 78,\n",
       " 53,\n",
       " 21,\n",
       " 19,\n",
       " 9,\n",
       " 20,\n",
       " 56,\n",
       " 44,\n",
       " 70]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# make a list of pseudo-random integers in [1, 99]\n",
    "ls = [ random.randint(1, 99) for _ in range(30) ]\n",
    "ls # show it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3,\n",
       " 9,\n",
       " 9,\n",
       " 12,\n",
       " 15,\n",
       " 18,\n",
       " 19,\n",
       " 19,\n",
       " 20,\n",
       " 21,\n",
       " 24,\n",
       " 32,\n",
       " 33,\n",
       " 44,\n",
       " 48,\n",
       " 50,\n",
       " 51,\n",
       " 53,\n",
       " 56,\n",
       " 56,\n",
       " 61,\n",
       " 63,\n",
       " 70,\n",
       " 78,\n",
       " 80,\n",
       " 81,\n",
       " 82,\n",
       " 83,\n",
       " 85,\n",
       " 95]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ls.sort() # sort the list in-place\n",
    "ls # show the sorted list; note there are some repeated elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The number 40 is not in the sorted list.  If it were, where would it go?\n",
    "bisect_left(ls, 40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3,\n",
       " 9,\n",
       " 9,\n",
       " 12,\n",
       " 15,\n",
       " 18,\n",
       " 19,\n",
       " 19,\n",
       " 20,\n",
       " 21,\n",
       " 24,\n",
       " 32,\n",
       " 33,\n",
       " 40,\n",
       " 44,\n",
       " 48,\n",
       " 50,\n",
       " 51,\n",
       " 53,\n",
       " 56,\n",
       " 56,\n",
       " 61,\n",
       " 63,\n",
       " 70,\n",
       " 78,\n",
       " 80,\n",
       " 81,\n",
       " 82,\n",
       " 83,\n",
       " 85,\n",
       " 95]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# insert it\n",
    "ls.insert(13, 40)\n",
    "ls # show the new list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The number 19 appears in the list multiple times.\n",
    "# Say we want a range [st, en) where st is the first element\n",
    "# (inclusive) and en is last element (exclusive) that contains a 19\n",
    "st, en = bisect_left(ls, 19), bisect_right(ls, 19)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6, 8)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st, en"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[19, 19]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ls[st:en]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Of course, there also exists a total ordering over strings\n",
    "# (lexicographical ordering), so we can do all the same things\n",
    "# with strings\n",
    "strls = ['a', 'awkward', 'awl', 'awls', 'axe', 'axes', 'bee']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strls == sorted(strls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 3)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# We want to get the range of elements that equal a query string:\n",
    "st, en = bisect_left(strls, 'awl'), bisect_right(strls, 'awl')\n",
    "st, en"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 4)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Say we want to get the range of elements that have some prefix,\n",
    "# e.g. 'aw' and say that 'z' is the lexicographically greatest\n",
    "# character in the alphabet.\n",
    "st, en = bisect_left(strls, 'aw'), bisect_left(strls, 'ax')\n",
    "st, en"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['awkward', 'awl', 'awls']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strls[st:en]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['$', 'a$', 'aaba$', 'aba$', 'abaaba$', 'ba$', 'baaba$']"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# If we can do it for any sorted list of strings, we can do it for\n",
    "# a sorted list of suffixes\n",
    "t = 'abaaba$'\n",
    "suffixes = sorted([t[i:] for i in range(len(t))])\n",
    "suffixes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 5)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st, en = bisect_left(suffixes, 'aba'), bisect_left(suffixes, 'abb')\n",
    "st, en"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}