My_binary_search_from_scratch.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of the current array: 12\n",
      "Length of the current array: 6\n",
      "Length of the current array: 2\n",
      "Length of the current array: 1\n",
      "\n",
      "-1\n",
      "\n",
      "Length of the current array: 12\n",
      "Length of the current array: 5\n",
      "Length of the current array: 2\n",
      "\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "\"\"\"You're going to write a binary search function.\n",
    "You should use an iterative approach - meaning\n",
    "using loops.\n",
    "Your function should take two inputs:\n",
    "a Python list to search through, and the value\n",
    "you're searching for.\n",
    "Assume the list only has distinct elements,\n",
    "meaning there are no repeated values, and \n",
    "elements are in a strictly increasing order.\n",
    "Return the index of value, or -1 if the value\n",
    "doesn't exist in the list.\"\"\"\n",
    "import numpy as np\n",
    "\n",
    "def binary_search_helper(input_array):\n",
    "    \"\"\"Your code goes here.\"\"\"\n",
    "    n=len(input_array)\n",
    "    even=False\n",
    "    if n%2==0:\n",
    "        center=n//2\n",
    "        even=True\n",
    "    else:\n",
    "        center=(n-1)//2\n",
    "    return center, even\n",
    "    \n",
    "def binary_search(input_array_, value):\n",
    "    input_array=input_array_.copy()\n",
    "    index=-1\n",
    "    Search=True\n",
    "    center=binary_search_helper(input_array)[0]\n",
    "    position=center\n",
    "    while(index==-1 and Search):\n",
    "        print(\"Length of the current array:\",len(input_array))\n",
    "        if input_array[center]>value:\n",
    "            input_array=input_array[:center]\n",
    "            center, even_left=binary_search_helper(input_array)\n",
    "            if even_left:\n",
    "                position -= center\n",
    "            else:\n",
    "                position -= center+1\n",
    "        elif input_array[center]<value:\n",
    "            input_array=input_array[center+1:]\n",
    "            center, even_left=binary_search_helper(input_array)\n",
    "            position += center+1\n",
    "        elif input_array[center]==value:\n",
    "            index=position\n",
    "        if len(input_array)==0:\n",
    "            Search=False\n",
    "    print()\n",
    "    return index\n",
    "test_list = [1,3,9,11,15,19,29,171,527.7,1472,-9,78]\n",
    "test_val1 = 17\n",
    "test_val2 = 527.7\n",
    "print(binary_search(test_list, test_val1))\n",
    "print()\n",
    "\n",
    "print(binary_search(test_list, test_val2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}