{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Basics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "arr = [12, 10, 92, 3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Search: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def linearSearch(arr, item):\n",
    "    return item in arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linear Search\n",
      "\n",
      "92: True\n",
      "22: False\n"
     ]
    }
   ],
   "source": [
    "print('Linear Search\\n\\n92: {}\\n22: {}'.format(linearSearch(arr, 92), linearSearch(arr, 22)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search: O(log n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def binarySearch(arr, low, high, item):\n",
    "    if high < low:\n",
    "        return -1\n",
    "    \n",
    "    mid = int(low + (high - low) / 2)    # Overflow Safe version of (low + high) / 2\n",
    "    \n",
    "    if item == arr[mid]:\n",
    "        return mid\n",
    "    \n",
    "    if item > arr[mid]:\n",
    "        return binarySearch(arr, (mid + 1), high, item)\n",
    "    \n",
    "    return binarySearch(arr, low, (mid - 1), item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index of 12 in [3, 10, 12, 92]: 2\n"
     ]
    }
   ],
   "source": [
    "sortedArr = arr[:]    # Or list(arr) - Shallow Copy\n",
    "sortedArr.sort()\n",
    "\n",
    "print(\"Index of {} in {}: {}\".format(12, sortedArr, binarySearch(sortedArr, 0, len(sortedArr), 12)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insert Unsorted: O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insertUnsorted(arr, item):\n",
    "    arr.append(item)\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before: [12, 10, 92, 3]\n",
      "After: [12, 10, 92, 3, 23]\n"
     ]
    }
   ],
   "source": [
    "print(\"Before: {}\".format(arr))\n",
    "print(\"After: {}\".format(insertUnsorted(arr, 23)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insert Sorted: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertSorted(arr, item):\n",
    "    i = len(arr) - 1\n",
    "    \n",
    "    while i >= 0 and arr[i] > item:\n",
    "        i -= 1\n",
    "        \n",
    "    arr.insert(i + 1, item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 3, 10, 12, 15, 92, 100]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insertSorted(sortedArr, 0)\n",
    "insertSorted(sortedArr, 15)\n",
    "insertSorted(sortedArr, 100)\n",
    "sortedArr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Delete Unsorted: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def deleteUnsorted(arr, item):\n",
    "    arr.remove(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 10, 92, 23]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deleteUnsorted(arr, 3)\n",
    "arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Delete Sorted: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def deleteSorted(arr, item):\n",
    "    i = binarySearch(arr, 0, len(arr), item)\n",
    "    \n",
    "    del arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 3, 10, 12, 15, 92]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deleteSorted(sortedArr, 100)\n",
    "sortedArr"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}