Searching Algos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 Not found\n"
     ]
    }
   ],
   "source": [
    "l = [1,2,3,4,5,6,7,8,9,0,11,12,13,114,33,44,55,66,77,88,99]\n",
    "\n",
    "x = 1000\n",
    "\n",
    "def linear_search(x, l):\n",
    "    print(\"Linear Search started!\")\n",
    "    for i in range(len(l)):\n",
    "        if l[i] == x:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "if linear_search(x,l):\n",
    "    print(x, \"Found\")\n",
    "else:\n",
    "    print(x, \"Not found\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search\n",
    "\n",
    "#### sorted sequence "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Binary search started!\n",
      "length of sequence 21\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 33, 44, 55, 66, 77, 88, 99, 114]\n",
      "10\n",
      "4\n",
      "1\n",
      "0\n",
      "-200 Not Found!!\n"
     ]
    }
   ],
   "source": [
    "l = [1,2,3,4,5,6,7,8,9,0,11,12,13,114,33,44,55,66,77,88,99]\n",
    "x = -200\n",
    "\n",
    "def binary_search(x,seq):\n",
    "    l=0\n",
    "    u=len(seq)-1\n",
    "    seq=sorted(seq)\n",
    "    print(seq)\n",
    "    while l <= u:\n",
    "        mid = (l+u)//2\n",
    "        print(mid)\n",
    "        if seq[mid] == x:\n",
    "            return True\n",
    "        elif seq[mid] > x:\n",
    "            u = mid-1\n",
    "        else:\n",
    "            l = mid+1\n",
    "    return False\n",
    "\n",
    "if True:\n",
    "    if binary_search(x,l):\n",
    "        print(x, \"Found!\")\n",
    "    else:\n",
    "        print(x, \"Not Found!!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 12, 23, 99, 222, 278, 1223, 2323]\n"
     ]
    }
   ],
   "source": [
    "def selection_sort(arr):\n",
    "    n=len(arr)\n",
    "    for i in range(n):\n",
    "        min_indx = i\n",
    "        for j in range(i+1, n):\n",
    "            if arr[j] < arr[min_indx]:\n",
    "                min_indx = j\n",
    "            \n",
    "        arr[min_indx], arr[i] = arr[i], arr[min_indx]\n",
    "    return arr\n",
    "\n",
    "l=[99,12,1223,2323,1,0,278,23,222]\n",
    "\n",
    "print(selection_sort(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(arr):\n",
    "    while True:\n",
    "        x=0\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                arr[i],arr[i+1] = arr[i+1], arr[i]\n",
    "                x=1\n",
    "        #x == 0 means, no swapping in this iteration of while loop ie. list is sorted\n",
    "        if x == 0:\n",
    "            break\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 12, 23, 99, 222, 278, 1223, 2323]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l=[99,12,1223,2323,1,0,278,23,222]\n",
    "bubble_sort(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "N=[1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 3]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[N.pop(1)]+N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#l=[4,3,7,1,8,2,0,5,78,34,12]\n",
    "def insertion_sort(l):\n",
    "    for i in range(1,len(l)):\n",
    "        flag1=0\n",
    "        flag2=0\n",
    "        for j in range(i-1,-1,-1):\n",
    "            if l[i]<l[j]:\n",
    "                flag1=1\n",
    "                continue\n",
    "            else:\n",
    "                flag2=1\n",
    "                break\n",
    "        if flag1==1:\n",
    "            key = l.pop(i)\n",
    "            if flag2 == 0:\n",
    "                l.insert(j,key)\n",
    "            else:\n",
    "                l.insert(j+1,key)\n",
    "    return l\n",
    "insertion_sort([4,3,7,1,8,0,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unsorted List ->  [99, 12, 1223, 2323, 1, 0, 278, 23, 222]\n"
     ]
    }
   ],
   "source": [
    "l=[99,12,1223,2323,1,0,278,23,222]\n",
    "print(\"Unsorted List -> \", l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unsorted List ->  [99, 12, 1223, 2323, 1, 0, 278, 23, 222]\n",
      "\n",
      "Selection sort: \n",
      "[0, 1, 12, 23, 99, 222, 278, 1223, 2323]\n",
      "\n",
      "Insertion sort: \n",
      "[0, 1, 12, 23, 99, 222, 278, 1223, 2323]\n"
     ]
    }
   ],
   "source": [
    "# selction sort\n",
    "\n",
    "def selection_sort(arr):\n",
    "\tprint()\n",
    "\tprint(\"Selection sort: \")\n",
    "\tn=len(arr)\n",
    "\tfor i in range(n):\n",
    "\t\tmin_indx = i\n",
    "\t\tfor j in range(i+1, n):\n",
    "\t\t\tif arr[j] < arr[min_indx]:\n",
    "\t\t\t\tmin_indx = j\n",
    "\t\t\t\n",
    "\t\tarr[min_indx], arr[i] = arr[i], arr[min_indx]\n",
    "\treturn arr\n",
    "\n",
    "def insertion_sort(l):\n",
    "\tprint()\n",
    "\tprint(\"Insertion sort: \")\n",
    "\tfor i in range(1,len(l)):\n",
    "\t\tflag1=0\n",
    "\t\tflag2=0\n",
    "\t\tfor j in range(i-1,-1,-1):\n",
    "\t\t\tif l[i]<l[j]:\n",
    "\t\t\t\tflag1=1\n",
    "\t\t\t\tcontinue\n",
    "\t\t\telse:\n",
    "\t\t\t\tflag2=1\n",
    "\t\t\t\tbreak\n",
    "\t\tif flag1==1:\n",
    "\t\t\tkey = l.pop(i)\n",
    "\t\t\tif flag2 == 0:\n",
    "\t\t\t\tl.insert(j,key)\n",
    "\t\t\telse:\n",
    "\t\t\t\tl.insert(j+1,key)\n",
    "\treturn l\n",
    "\n",
    "l=[99,12,1223,2323,1,0,278,23,222]\n",
    "print(\"Unsorted List -> \", l)\n",
    "print(selection_sort(l))\n",
    "print(insertion_sort(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Book():\n",
    "    def __init__(self, name, writer, pages):\n",
    "        self.name = name\n",
    "        self.writer = writer\n",
    "        self.pages = pages\n",
    "    def __len__(self):\n",
    "        print(self.pages)\n",
    "    def __str__(self):\n",
    "        print(self.name)\n",
    "    #def __repr__(self):\n",
    "    #    print(self.name)\n",
    "    def __del__(self):\n",
    "        print( \"the book is deleted\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = Book(\"potter\",\"rowling\", 329)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Book at 0x2883d0f4a08>"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "kd\n",
      "kdk\n",
      "dk\n",
      "sd\n",
      "sdf\n",
      "sdfg\n",
      "sdfgf\n",
      "sdfgfd\n",
      "sdfgfds\n",
      "df\n",
      "dfg\n",
      "dfgf\n",
      "dfgfd\n",
      "dfgfds\n",
      "fg\n",
      "fgf\n",
      "fgfd\n",
      "fgfds\n",
      "gf\n",
      "gfd\n",
      "gfds\n",
      "fd\n",
      "fds\n",
      "ds\n",
      "\n",
      "Longest palindrome subString is: sdfgfds\n",
      "Length is:  7\n"
     ]
    }
   ],
   "source": [
    "s=\"apkdksdfgfdsjwhfowe\"\n",
    "\n",
    "for i in range(0, len(s)-2):\n",
    "    for j in range(i+2,len(s)):\n",
    "        key=s[i:j][::-1]\n",
    "        len_key=len(key)\n",
    "        if key in s:\n",
    "            print(s[i:j])\n",
    "            \n",
    "            \n",
    "# A Python3 solution for longest palindrome\n",
    "\n",
    "# Function to pra subString str[low..high]\n",
    "def printSubStr(str, low, high):\n",
    "\t\n",
    "\tfor i in range(low, high + 1):\n",
    "\t\tprint(str[i], end = \"\")\n",
    "\n",
    "# This function prints the\n",
    "# longest palindrome subString\n",
    "# It also returns the length\n",
    "# of the longest palindrome\n",
    "def longestPalSubstr(str):\n",
    "\t\n",
    "\t# Get length of input String\n",
    "\tn = len(str)\n",
    "\t\n",
    "\t# All subStrings of length 1\n",
    "\t# are palindromes\n",
    "\tmaxLength = 1\n",
    "\tstart = 0\n",
    "\t\n",
    "\t# Nested loop to mark start\n",
    "\t# and end index\n",
    "\tfor i in range(n):\n",
    "\t\tfor j in range(i, n):\n",
    "\t\t\tflag = 1\n",
    "\t\t\t\n",
    "\t\t\t# Check palindrome\n",
    "\t\t\tfor k in range(0, ((j - i) // 2) + 1):\n",
    "\t\t\t\tif (str[i + k] != str[j - k]):\n",
    "\t\t\t\t\tflag = 0\n",
    "\n",
    "\t\t\t# Palindrome\n",
    "\t\t\tif (flag != 0 and (j - i + 1) > maxLength):\n",
    "\t\t\t\tstart = i\n",
    "\t\t\t\tmaxLength = j - i + 1\n",
    "\t\t\t\t\n",
    "\tprint(\"Longest palindrome subString is: \", end = \"\")\n",
    "\tprintSubStr(str, start, start + maxLength - 1)\n",
    "\n",
    "\t# Return length of LPS\n",
    "\treturn maxLength\n",
    "\n",
    "# Driver Code\n",
    "if __name__ == '__main__':\n",
    "\tprint()\n",
    "\tstr = \"apkdksdfgfdsjwhfowe\"\n",
    "\t\n",
    "\tprint(\"\\nLength is: \", longestPalSubstr(str))\n",
    "\n",
    "# This code is contributed by 29AjayKumar\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s[0:2][::-1] in s[2:2+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "6\n",
      "string!\n",
      "4\n",
      "2\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "a=8\n",
    "while a >= 0:\n",
    "    if a%2 == 0:\n",
    "        print(a)\n",
    "    if a == 5:\n",
    "        print(\"string!\")\n",
    "    a-=1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "12\n",
      "123\n"
     ]
    }
   ],
   "source": [
    "s=0\n",
    "i=''\n",
    "for _ in \"111\":\n",
    "    s+=1\n",
    "    i+=str(s)\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def func(a):\n",
    "    return(a-1)**4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "func(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 7,  3,  1,  5],\n",
       "       [ 7,  8,  3,  6],\n",
       "       [ 5,  8, 10,  5],\n",
       "       [ 1,  1,  9,  2]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "numpy.random.randint(1,12,(4,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_recursive(L):\n",
    "    if len(L) == 1:\n",
    "        return L[0]\n",
    "\n",
    "    idx = len(L) // 2\n",
    "    return sum_recursive(L[:idx]) + sum_recursive(L[idx:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_recursive([1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_arr(arr,num, level=0):\n",
    "    if num==0:\n",
    "        print(\"num to be added: \", 0, \"At level:\", level)\n",
    "        return 0\n",
    "    else:\n",
    "        print(\"%d + sum_arr(%d, num-1, level=level+1)\" % {arr[num-1], arr})\n",
    "        print(\"num to be added: \", arr[num-1], \"At level:\", level)\n",
    "        return arr[num-1] + sum_arr(arr, num-1, level=level+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "not enough arguments for format string",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-46-540f3c5209a3>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0msum_arr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-45-7b38df09b437>\u001b[0m in \u001b[0;36msum_arr\u001b[1;34m(arr, num, level)\u001b[0m\n\u001b[0;32m      4\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 6\u001b[1;33m         \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"%d + sum_arr(%d, num-1, level=level+1)\"\u001b[0m \u001b[1;33m%\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnum\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      7\u001b[0m         \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"num to be added: \"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnum\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"At level:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mlevel\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnum\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0msum_arr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0marr\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mnum\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mlevel\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mlevel\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: not enough arguments for format string"
     ]
    }
   ],
   "source": [
    "sum_arr([1,2,3], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type([1,2,3]) is list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def power(a,b):\n",
    "    if b == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return a*power(a,b-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "81"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "power(3,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "None is \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}