08-Binary-Search.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"Binary_Search.ipynb","provenance":[],"collapsed_sections":[],"authorship_tag":"ABX9TyNPNoPs82DO+mb+A+5mw8To"},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"lhbUt2MOioqk"},"source":["* Import Statement\r\n","* Creating a list --> unique and orderd slightly random list --> near to real world example"]},{"cell_type":"code","metadata":{"id":"7L_HLWFpWjka"},"source":["from random import randint\r\n","random_set = set()\r\n","for i in range(-1000, 1001, 5):\r\n","    sort_set = randint(0,1000)\r\n","    random_set.add(sort_set)\r\n","\r\n","random_list = sorted(list(random_set))\r\n","random_list"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"4hx593VGjLwN"},"source":["Defining the function for naive or normal search, mostly this is for loop thing"]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"az4lfUN0VDyk","executionInfo":{"status":"ok","timestamp":1608276050967,"user_tz":-330,"elapsed":975,"user":{"displayName":"Kannan Ravindran","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14Gh_Xq8TkqqOG9awGEcxqYQ7IMlOg8-xjzNMO9wnnA=s64","userId":"14593321298634751198"}},"outputId":"45ee3994-4a34-4b26-d8e0-aa9f2641d403"},"source":["def normal_search(find, sorted_list):\r\n","    for i, v in enumerate(sorted_list):\r\n","        if v == find:\r\n","            return i\r\n","\r\n","print(normal_search(995, random_list))\r\n","len(random_list)"],"execution_count":16,"outputs":[{"output_type":"stream","text":["326\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["328"]},"metadata":{"tags":[]},"execution_count":16}]},{"cell_type":"markdown","metadata":{"id":"aKWkQukuy_q6"},"source":["* Defining the binary search function"]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"YAvjAaKcnHVG","executionInfo":{"status":"ok","timestamp":1608276014471,"user_tz":-330,"elapsed":999,"user":{"displayName":"Kannan Ravindran","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14Gh_Xq8TkqqOG9awGEcxqYQ7IMlOg8-xjzNMO9wnnA=s64","userId":"14593321298634751198"}},"outputId":"069775bd-7530-4ef1-8045-d9a4feb1b7ec"},"source":["l = 0\r\n","h = len(random_list) - 1\r\n","\r\n","def binary_search(high, low, sorted_list, find):\r\n","\r\n","    mid_value = (low + high) // 2\r\n","    if high >= low:\r\n","\r\n","        if find == sorted_list[mid_value]:\r\n","            return mid_value\r\n","\r\n","        elif find > sorted_list[mid_value]:\r\n","            return binary_search(high,mid_value + 1, sorted_list, find)\r\n","\r\n","        elif find < sorted_list[mid_value]:\r\n","            return binary_search(mid_value -1 , low, sorted_list, find)\r\n","    else:\r\n","        return f\"OOP's Your element is not present in the memory\"\r\n","\r\n","binary_search(h, l, random_list, 995)"],"execution_count":13,"outputs":[{"output_type":"execute_result","data":{"text/plain":["326"]},"metadata":{"tags":[]},"execution_count":13}]},{"cell_type":"markdown","metadata":{"id":"X0Ubd5S7zHFa"},"source":["* Using time module to check the time"]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"cFobMuK4rvJb","executionInfo":{"status":"ok","timestamp":1608277090989,"user_tz":-330,"elapsed":956,"user":{"displayName":"Kannan Ravindran","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14Gh_Xq8TkqqOG9awGEcxqYQ7IMlOg8-xjzNMO9wnnA=s64","userId":"14593321298634751198"}},"outputId":"b79f12dc-b5b2-42b5-ee61-cc969a05ac53"},"source":["from time import time\r\n","\r\n","beginning1 = time()\r\n","print(normal_search(995, random_list))\r\n","ending1 = time()\r\n","print(\"Time taken for Normal Search is \", ending1 - beginning1)\r\n","\r\n","beginning = time()\r\n","print(binary_search(h, l, random_list, 995))\r\n","ending = time()\r\n","print(\"Time taken for binary search is \", ending - beginning)"],"execution_count":31,"outputs":[{"output_type":"stream","text":["326\n","Time taken for Normal Search is  0.00016951560974121094\n","326\n","Time taken for binary search is  7.653236389160156e-05\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"S-pUdmEI7i0X"},"source":["Down here i modify something and put all the code in the single cell\r\n","* Upgraded to 10,000 numbers\r\n","* Getting number from user to find their number"]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"PivjhJzU7jQK","executionInfo":{"status":"ok","timestamp":1608279633001,"user_tz":-330,"elapsed":5568,"user":{"displayName":"Kannan Ravindran","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14Gh_Xq8TkqqOG9awGEcxqYQ7IMlOg8-xjzNMO9wnnA=s64","userId":"14593321298634751198"}},"outputId":"94245912-fce7-4d82-c247-6856f3503723"},"source":["from random import randint\r\n","from time import time\r\n","\r\n","random_set = set()\r\n","for i in range(-1000, 10001, 5):\r\n","    sort_set = randint(0,10000)\r\n","    random_set.add(sort_set)\r\n","random_list = sorted(list(random_set))\r\n","\r\n","\r\n","l = 0\r\n","h = len(random_list) - 1\r\n","def binary_search(high, low, sorted_list, find):\r\n","\r\n","    mid_value = (low + high) // 2\r\n","    if high >= low:\r\n","\r\n","        if find == sorted_list[mid_value]:\r\n","            return mid_value\r\n","\r\n","        elif find > sorted_list[mid_value]:\r\n","            return binary_search(high,mid_value + 1, sorted_list, find)\r\n","\r\n","        elif find < sorted_list[mid_value]:\r\n","            return binary_search(mid_value -1 , low, sorted_list, find)\r\n","    else:\r\n","        return f\"OOP's Your element is not present in the memory\"\r\n","\r\n","\r\n","def normal_search(find, sorted_list):\r\n","    for i, v in enumerate(sorted_list):\r\n","        if v == find:\r\n","            return i\r\n","        else:\r\n","            return \"OOP's your element is not present in the memory\"\r\n","\r\n","find_number = int(input(\"Enter your number to search between 0 to 10,000: \"))\r\n","print(\"\\n\")\r\n","\r\n","beginning1 = time()\r\n","print(normal_search(find_number, random_list))\r\n","ending1 = time()\r\n","normal_time = ending1 - beginning1\r\n","print(f\"Time taken for 'Normal Search' is {normal_time} \\n\")\r\n","\r\n","beginning = time()\r\n","print(binary_search(h, l, random_list, find_number))\r\n","ending = time()\r\n","binary_time = ending - beginning\r\n","print(f\"Time taken for 'Binary search' is {binary_time} \\n\")\r\n","\r\n","diff = normal_time - binary_time\r\n","print(f\"{diff} seconds differnce between binary search and normal search \\n\")\r\n","\r\n","if diff < 0:\r\n","    print(\"You number is present beginning of random number list, so it normal or naive search finds that easily, try entering large number \")\r\n","else:\r\n","    print(\"See I told you, binary search is faster when your number is present last in the list\")"],"execution_count":32,"outputs":[{"output_type":"stream","text":["Enter your number to search between 0 to 10,000: 9000\n","\n","\n","OOP's your element is not present in the memory\n","Time taken for 'Normal Search' is 0.00010037422180175781 \n","\n","1787\n","Time taken for 'Binary search' is 9.870529174804688e-05 \n","\n","1.6689300537109375e-06 seconds differnce between binary search and normal search \n","\n","See I told you, binary search is faster when your number is present last in the list\n"],"name":"stdout"}]}]}