Exponential Search.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##############################################\n",
    "# Exponential Search using Python\n",
    "# By Giriraj Vaishnav \n",
    "##############################################\n",
    " \n",
    "# A recurssive binary search function returns\n",
    "# location  of x in given array arr[l..r] is\n",
    "# present, otherwise -1\n",
    "def binarySearch( arr, l, r, x):\n",
    "    if r >= l:\n",
    "        mid = l + ( r-l ) / 2\n",
    "         \n",
    "        # If the element is present at\n",
    "        # the middle itself\n",
    "        if arr[mid] == x:\n",
    "            return mid\n",
    "         \n",
    "        # If the element is smaller than mid,\n",
    "        # then it can only be present in the\n",
    "        # left subarray\n",
    "        if arr[mid] > x:\n",
    "            return binarySearch(arr, l,\n",
    "                                mid - 1, x)\n",
    "         \n",
    "        # Else he element can only be\n",
    "        # present in the right\n",
    "        return binarySearch(arr, mid + 1, r, x)\n",
    "         \n",
    "    # We reach here if the element is not present\n",
    "    return -1\n",
    " \n",
    "# Returns the position of first\n",
    "# occurrence of x in array\n",
    "def exponentialSearch(arr, n, x):\n",
    "    # IF x is present at first\n",
    "    # location itself\n",
    "    if arr[0] == x:\n",
    "        return 0\n",
    "         \n",
    "    # Find range for binary search\n",
    "    # j by repeated doubling\n",
    "    i = 1\n",
    "    while i < n and arr[i] <= x:\n",
    "        i = i * 2\n",
    "     \n",
    "    # Call binary search for the found range\n",
    "    return binarySearch( arr, i / 2,\n",
    "                         min(i, n-1), x)\n",
    "     \n",
    " \n",
    "# Driver Code\n",
    "arr = [2, 3, 4, 10, 40]\n",
    "n = len(arr)\n",
    "x = 10\n",
    "result = exponentialSearch(arr, n, x)\n",
    "if result == -1:\n",
    "    print \"Element not found in thye array\"\n",
    "else:\n",
    "    print \"Element is present at index %d\" %(result)"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}