{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Foundations of Computational Economics #11\n", "\n", "by Fedor Iskhakov, ANU\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## Binary search algorithm\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "\n", "[https://youtu.be/eTmQBpN-eyk](https://youtu.be/eTmQBpN-eyk)\n", "\n", "Description: Binary search. Other divide and conquer algorithms. Recursion." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Divide and conquer algorithms (DAC)\n", "\n", "1. **Divide** the problem into subproblems \n", "1. **Solve/conquer** each subproblem recursively \n", "1. **Combine** solutions of subproblems together " ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# simple example of DAC algorithm\n", "def sum_list(l):\n", " '''Summing the elements of the list using DAC algorithm\n", " '''\n", " pass\n", "\n", "sum_list(list(range(16)))" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "dividing [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] into [0, 1, 2, 3, 4, 5, 6, 7] and [8, 9, 10, 11, 12, 13, 14, 15]\n", "dividing [0, 1, 2, 3, 4, 5, 6, 7] into [0, 1, 2, 3] and [4, 5, 6, 7]\n", "dividing [0, 1, 2, 3] into [0, 1] and [2, 3]\n", "dividing [0, 1] into [0] and [1]\n", "sum of [0, 1] is 1.00\n", "dividing [2, 3] into [2] and [3]\n", "sum of [2, 3] is 5.00\n", "sum of [0, 1, 2, 3] is 6.00\n", "dividing [4, 5, 6, 7] into [4, 5] and [6, 7]\n", "dividing [4, 5] into [4] and [5]\n", "sum of [4, 5] is 9.00\n", "dividing [6, 7] into [6] and [7]\n", "sum of [6, 7] is 13.00\n", "sum of [4, 5, 6, 7] is 22.00\n", "sum of [0, 1, 2, 3, 4, 5, 6, 7] is 28.00\n", "dividing [8, 9, 10, 11, 12, 13, 14, 15] into [8, 9, 10, 11] and [12, 13, 14, 15]\n", "dividing [8, 9, 10, 11] into [8, 9] and [10, 11]\n", "dividing [8, 9] into [8] and [9]\n", "sum of [8, 9] is 17.00\n", "dividing [10, 11] into [10] and [11]\n", "sum of [10, 11] is 21.00\n", "sum of [8, 9, 10, 11] is 38.00\n", "dividing [12, 13, 14, 15] into [12, 13] and [14, 15]\n", "dividing [12, 13] into [12] and [13]\n", "sum of [12, 13] is 25.00\n", "dividing [14, 15] into [14] and [15]\n", "sum of [14, 15] is 29.00\n", "sum of [12, 13, 14, 15] is 54.00\n", "sum of [8, 9, 10, 11, 12, 13, 14, 15] is 92.00\n", "sum of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] is 120.00\n" ] }, { "data": { "text/plain": [ "120" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# simple example of DAC algorithm\n", "def sum_list(l):\n", " '''Summing the elements of the list using DAC algorithm\n", " '''\n", " if len(l)==1:\n", " return l[0] # sum of list of one element\n", " j = len(l)//2 # devide list in two\n", " print('dividing %r into %r and %r' % (l,l[:j],l[j:]), flush=True)\n", " s = sum_list(l[:j]) + sum_list(l[j:])\n", " print('sum of %r is %1.2f' % (l,s), flush=True)\n", " return s\n", "\n", "sum_list(list(range(16)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Complexity of DAC\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Typical DAC algorithms\n", "\n", "- Binary search \n", "- Quicksort and merge sort \n", "- Fast Fourier transform (FTT) algorithm \n", "- Karatsuba fast multiplication algorithm " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Binary search\n", "\n", "Inputs: sorted list of numbers, and a value to find\n", "\n", "1. Find middle point \n", "1. If the sought value is below, reduce the list to the lower half \n", "1. If the sought value is above, reduce the list to the upper half " ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "def binary_search(list=[0,1],val=0):\n", " pass" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "list = [ 1 18 27 28 33 35 39 41 50 52 56 61 75 89 94 99]\n", "searching for [52]\n", "step 0: gr[i1=0]=1, gr[i2=15]=99, gr[j=7]=41\n", "step 1: gr[i1=7]=41, gr[i2=15]=99, gr[j=11]=61\n", "step 2: gr[i1=7]=41, gr[i2=11]=61, gr[j=9]=52\n", "Searched for 52, found x[9]=52\n" ] } ], "source": [ "import numpy as np\n", "N = 16\n", "# random sorted sequence of integers up to 100\n", "x = np.random.choice(100,size=N,replace=False)\n", "x = np.sort(x)\n", "# random choice of one number/index\n", "k0 = np.random.choice(N,size=1)\n", "\n", "k1 = binary_search(list=x,val=x[k0])\n", "print(\"Searched for %d, found x[%d]=%d\"%(x[k0],k1,x[k1]))" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "def binary_search(list=[0,1],val=0,verbose=True):\n", " '''Returns the index of val on the sorted list\n", " Optional delay introduces a delay (in microsecond)\n", " '''\n", " i1,i2 = 0,len(list)-1\n", " if val==list[i1]: return i1\n", " if val==list[i2]: return i2\n", " j=(i1+i2)//2\n", " if verbose:\n", " print('list =',list)\n", " print('searching for',val)\n", " k=0\n", " print('step %d: gr[i1=%d]=%d, gr[i2=%d]=%d, gr[j=%d]=%d' % (k,i1,list[i1],i2,list[i2],j,list[j]))\n", " while list[j]!=val:\n", " if val>list[j]:\n", " i1 = j\n", " else:\n", " i2 = j\n", " j = (i1+i2)//2 # divide in half\n", " if verbose:\n", " k +=1\n", " print('step %d: gr[i1=%d]=%d, gr[i2=%d]=%d, gr[j=%d]=%d' % (k,i1,list[i1],i2,list[i2],j,list[j]))\n", " return j" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Further learning resources\n", "\n", "- Divide and conquer algorithms by Brandon Skerritt\n", " [https://skerritt.blog/divide-and-conquer-algorithms/](https://skerritt.blog/divide-and-conquer-algorithms/) " ] } ], "metadata": { "celltoolbar": "Slideshow", "date": 1612589584.667138, "download_nb": false, "filename": "11_alg_binary_search.rst", "filename_with_path": "11_alg_binary_search", "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" }, "title": "Foundations of Computational Economics #11" }, "nbformat": 4, "nbformat_minor": 4 }