Skip to content

Instantly share code, notes, and snippets.

@BSCdfdff

BSCdfdff/Array Binary Search.ipynb

Created March 19, 2020 08:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save BSCdfdff/f9e5634861b5e2ef0fde0291ca8df8f2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save BSCdfdff/f9e5634861b5e2ef0fde0291ca8df8f2 to your computer and use it in GitHub Desktop.
Download ZIP
Array Binary Search
Display the source blob
Display the rendered blob
Raw
Array Binary Search.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Array ADT\n",
"\n",
"+ Binary Search"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Binary Search\n",
"\n",
"___\n",
"\n",
"Size = 15\n",
"\n",
"Length = 15\n",
"\n",
"How to read the table:\n",
"\n",
"1. First row contains the value(s)\n",
"2. Second row contains the index\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"The table must be be sorted.\n",
"\n",
"The value we search for we call key=5.\n",
"\n",
"Why is it called binary search? It will check for a key element in the middle of sorted list. That is it will split the list into 2.\n",
"\n",
"\n",
"\n",
"___\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Search for key element 18 (Succesful)\n",
"\n",
"___\n",
"\n",
"We will need three index variables:\n",
"\n",
"l = low = lowest index\n",
"\n",
"h=high = highest index\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$$$\n",
"\n",
"m= mid = low + hight divided by 2 (and we take the floor value)\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&\\T&_{mid}\\T&\\T&\\T&\\T&\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"$$$$\n",
"\n",
"Is the $\\text {key}=18$ equal to $mid$? No.\n",
"\n",
"Is $\\text {key}=18$ larger of or less than $\\text {index}= 7 = 27$ ?\n",
"\n",
"It is less than $27$, so we set the higher index, $h$ to $mid - 1$, which is equal to $\\text {index } 6$. And $l$ remains at 0.\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&_h\\T&_{mid}\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$$$\n",
"\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline\n",
"0\\T&6\\T&{(0+6)\\over 2}\\T&3 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&_{mid}\\T&\\T&\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$$$\n",
"\n",
"Is the $\\text {key}=18$ equal to $mid$? No.\n",
"\n",
"Is $\\text {key}=18$ larger of or less than $\\text {index}= 3 = 15$ ?\n",
"\n",
"It is greater than $15$, so we set the lower index, $l$ to $mid + 1$, which is equal to $\\text {index } 4$. And $h$ remains at $6$.\n",
"\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&_{mid}\\T&_l\\T&\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline\n",
"0\\T&6\\T&{(0+6)\\over 2}\\T&3 \\\\\\hline \n",
"4\\T&6\\T&{(4+6)\\over 2}\\T&5 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&_l\\T&_{mid}\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"N\n",
"\n",
"$$$$\n",
"\n",
"Is the $\\text {key}=18$ equal to $mid$? No.\n",
"\n",
"Is $\\text {key}=18$ larger of or less than $\\text {index}= 5 = 21$ ?\n",
"\n",
"It is less than $21$, so we set the higher index, $h$ to $mid -1$, which is equal to $\\text {index } 4$. And $l$ remains at $4$.\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&_l + _h\\T&_{mid}\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"Now high and low is on index $4$, value $18$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline\n",
"0\\T&6\\T&{(0+6)\\over 2}\\T&3 \\\\\\hline \n",
"4\\T&6\\T&{(4+6)\\over 2}\\T&5 \\\\\\hline \n",
"4\\T&4\\T&{(4+4)\\over 2}\\T&4 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&_l/_h/_{mid}\\T&\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"Is the $\\text {key}=18$ equal to $mid$? \n",
"\n",
"Yes element found at index $4$.\n",
"\n",
"\n",
"How many comparison's done? Four.\n",
"\n",
"With linear search we found the element in Five\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Search for key element 34 (Succesful)\n",
"\n",
"___\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&\\T&_{mid}\\T&\\T&\\T&\\T&\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&_l\\T&\\T&\\T&\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"8\\T&14\\T&{(8+14)\\over 2}\\T&11 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&_l\\T&\\T&\\T&_{mid}\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&_l\\T&\\T&_h\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"8\\T&10\\T&{(8+10)\\over 2}\\T&9 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&_l\\T&_{mid}\\T&_h\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"Mid = index 10 = 34. Found\n",
"\n",
"Number of searches: $4$\n",
"Number of linear searches :$11$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Search for key element 25 (Unsuccesful)\n",
"\n",
"___\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&\\T&_{mid}\\T&\\T&\\T&\\T&\\T&\\T&\\T&_h \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&\\T&\\T&\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"0\\T&6\\T&{(0+6)\\over 2}\\T&3 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"_l\\T&\\T&\\T&_{mid}\\T&\\T&\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&_l\\T&\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"0\\T&6\\T&{(0+6)\\over 2}\\T&3 \\\\\\hline \n",
"4\\T&6\\T&{(4+6)\\over 2}\\T&5 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&_l\\T&_{mid}\\T&_h\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&\\T&\\T&_h/_l\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|}\n",
"\\hline \n",
"l\\T&h\\T&{(l+h)\\over 2} \\T&\\text {mid} \\\\\\hline \n",
"0\\T&14\\T&{(0+14)\\over 2}\\T&7 \\\\\\hline \n",
"0\\T&6\\T&{(0+6)\\over 2}\\T&3 \\\\\\hline \n",
"4\\T&6\\T&{(4+6)\\over 2}\\T&5 \\\\\\hline \n",
"6\\T&6\\T&{(6+6)\\over 2}\\T&6 \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&\\T&\\T&_h/_l/_{mid}\\T&\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\T&\\T&\\T&\\T&\\T&\\T&_h\\T&_l\\T&\\T&\\T&\\T&\\T&\\T&\\T& \\\\\\hline \n",
"\\end{array}\n",
"$$\n",
"\n",
"Here we stop as $l$ becomes greater than $h$\n",
"\n",
"\n",
"It took 4 comparisons, we do not count the last one."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Coding Example\n",
"\n",
"$$\n",
"\\newcommand\\T{\\Rule{0pt}{1em}{.3em}}\n",
"\\begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\n",
"\\hline \n",
"4\\T&8\\T&10\\T&15\\T&18\\T&21\\T&24\\T&27\\T&29\\T&33\\T&34\\T&37\\T&39\\T&41\\T&43 \\\\\\hline \n",
"_0\\T&_1\\T&_2\\T&_3\\T&_4\\T&_5\\T&_6\\T&_7\\T&_8\\T&_9\\T&_{10}\\T&_{11}\\T&_{12}\\T&_{13}\\T&_{14} \\\\\\hline \n",
"\\end{array}\n",
"$$\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"#include <iostream>\n",
"#include <climits>\n",
"#include <math.h>\n",
"using namespace std;"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"class Array{\n",
"private:\n",
" int *A;\n",
" int size;\n",
" int length;\n",
"public:\n",
" Array(){\n",
" size=10;\n",
" A=new int[10];\n",
" length = 0;\n",
" \n",
" }\n",
" Array(int sz){\n",
" size=sz;\n",
" A=new int[sz];\n",
" length = 0;\n",
" \n",
" }\n",
" ~Array(){\n",
" delete []A;\n",
" }\n",
" void Display();\n",
" void Insert (int index, int x);\n",
" int BinarySearch(int key);\n",
" int BinarySearchRecursive(int l, int h, int key);\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"int Array::BinarySearch(int key){\n",
" int mid; \n",
" int l = 0;\n",
" int h = length-1; \n",
" while (l<=h){ \n",
" mid = (l+h)/2;\n",
" if(key==A[mid])\n",
" return mid;\n",
" else if (key<A[mid])\n",
" h = mid-1;\n",
" else\n",
" l = mid+1;\n",
" }\n",
" return -1; \n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## This is an example of Tail Recursion\n",
"\n",
"As we know where we have tail recursion, its better to choose the loop."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"int Array::BinarySearchRecursive(int l, int h, int key){\n",
" int mid; \n",
" \n",
" if (l<=h){ \n",
" mid = (l+h)/2;\n",
" if(key==A[mid])\n",
" return mid;\n",
" else if (key<A[mid])\n",
" return BinarySearchRecursive(l,mid-1,key);\n",
" else\n",
" return BinarySearchRecursive(mid+1,h,key);\n",
" }\n",
" return -1; \n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"void Array::Insert(int index, int x){\n",
" if (index>=0 && index<=length){\n",
" for(int i=length-1;i>=index;i--)\n",
" A[i+1]=A[i];\n",
" A[index]=x;\n",
" length++; \n",
" }\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"void Array::Display(){\n",
" for(int i=0; i<length;i++)\n",
" cout<<A[i]<<\" \"; \n",
" cout<<endl; \n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"Array arr(14);\n",
"arr.Insert(0,4);\n",
"arr.Insert(1,8);\n",
"arr.Insert(2,10);\n",
"arr.Insert(3,15);\n",
"arr.Insert(4,18);\n",
"arr.Insert(5,21);\n",
"arr.Insert(6,24);\n",
"arr.Insert(7,27);\n",
"arr.Insert(8,29);\n",
"arr.Insert(9,33);\n",
"arr.Insert(10,34);\n",
"arr.Insert(11,37);\n",
"arr.Insert(12,39);\n",
"arr.Insert(13,41);\n",
"arr.Insert(14,43);\n"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4 8 10 15 18 21 24 27 29 33 34 37 39 41 43 \n"
]
}
],
"source": [
"arr.Display();"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"//cout<<arr.LinearSearch(5)<<endl;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pointer is not at the beginning, so either do normal Binsearch or Recursive cant do both"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10\n"
]
}
],
"source": [
"//cout<<arr.BinarySearch(34)<<endl;"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cout<<arr.BinarySearchRecursive(0,14,34)<<endl;"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "C++17",
"language": "C++17",
"name": "xcpp17"
},
"language_info": {
"codemirror_mode": "text/x-c++src",
"file_extension": ".cpp",
"mimetype": "text/x-c++src",
"name": "c++",
"version": "-std=c++17"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment