{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c908d4cf-4eca-4ed1-aea1-40838991417a",
   "metadata": {},
   "source": [
    "# Searching Algorithm\n",
    "(Interpolation, KMP, Boyer-Moore, Jump Search, Exponential)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1f979614-7cb6-4105-8160-3e4d03ff0788",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Target 18 found at index 4.\n"
     ]
    }
   ],
   "source": [
    "def interpolation_search(arr, target):\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    \n",
    "    while low <= high and target >= arr[low] and target <= arr[high]:\n",
    "        # Calculate mid using interpolation formula\n",
    "        mid = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))\n",
    "        \n",
    "        if arr[mid] == target:\n",
    "            return mid\n",
    "        \n",
    "        if arr[mid] < target:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid - 1\n",
    "    \n",
    "    return -1\n",
    "\n",
    "# Dataset\n",
    "data = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]\n",
    "# Target\n",
    "target = 18\n",
    "\n",
    "# Call the interpolation_search function\n",
    "result = interpolation_search(data, target)\n",
    "\n",
    "if result != -1:\n",
    "    print(f\"Target {target} found at index {result}.\")\n",
    "else:\n",
    "    print(f\"Target {target} not found in the dataset.\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d740d76a-41ae-4c9a-9d3f-c605bea6aec2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_lps_array(pattern):\n",
    "    length = 0\n",
    "    i = 1\n",
    "    lps = [0] * len(pattern)\n",
    "    \n",
    "    while i < len(pattern):\n",
    "        if pattern[i] == pattern[length]:\n",
    "            length += 1\n",
    "            lps[i] = length\n",
    "            i += 1\n",
    "        else:\n",
    "            if length != 0:\n",
    "                length = lps[length - 1]\n",
    "            else:\n",
    "                lps[i] = 0\n",
    "                i += 1\n",
    "    return lps\n",
    "\n",
    "def kmp_search(text, pattern):\n",
    "    lps = compute_lps_array(pattern)\n",
    "    \n",
    "    i = j = 0\n",
    "    positions = []\n",
    "    \n",
    "    while i < len(text):\n",
    "        if pattern[j] == text[i]:\n",
    "            i += 1\n",
    "            j += 1\n",
    "            \n",
    "            if j == len(pattern):\n",
    "                positions.append(i - j)\n",
    "                j = lps[j - 1]\n",
    "        else:\n",
    "            if j != 0:\n",
    "                j = lps[j - 1]\n",
    "            else:\n",
    "                i += 1\n",
    "                \n",
    "    return positions\n",
    "\n",
    "# Text\n",
    "text = \"ABABDABACDABABCABAB\"\n",
    "# Pattern\n",
    "pattern = \"ABABCABAB\"\n",
    "\n",
    "# Call the kmp_search function\n",
    "positions = kmp_search(text, pattern)\n",
    "\n",
    "if positions:\n",
    "    print(f\"Pattern found at indices: {positions}\")\n",
    "else:\n",
    "    print(\"Pattern not found in the text.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd0f2de0-8015-4572-bc84-8ec140022889",
   "metadata": {},
   "source": [
    "Dalam kode di atas, fungsi compute_lps_array menghitung tabel LPS (Longest Prefix Suffix) untuk pola yang diberikan. Fungsi kmp_search melakukan pencarian pola dalam teks menggunakan algoritma KMP dan mengumpulkan posisi di mana pola cocok dalam list positions.\n",
    "\n",
    "Setelah menginisialisasi teks dan pola yang akan dicari, kita memanggil fungsi kmp_search dan mencetak posisi di mana pola ditemukan dalam teks. Jika tidak ditemukan, pesan yang sesuai akan dicetak."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "24f5a72f-42e4-40f7-a5ec-ba41030d12e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bad_character_table(pattern):\n",
    "    table = {}\n",
    "    for i in range(len(pattern)):\n",
    "        table[pattern[i]] = i\n",
    "    return table\n",
    "\n",
    "def boyer_moore_search(text, pattern):\n",
    "    bad_char_table = bad_character_table(pattern)\n",
    "    m = len(pattern)\n",
    "    n = len(text)\n",
    "    i = m - 1\n",
    "\n",
    "    while i < n:\n",
    "        k = 0\n",
    "        while k < m and pattern[m - 1 - k] == text[i - k]:\n",
    "            k += 1\n",
    "        if k == m:\n",
    "            return i - m + 1\n",
    "        else:\n",
    "            bad_char_shift = i - m + 1 + bad_char_table.get(text[i], -1)\n",
    "            i += max(1, m - bad_char_shift)\n",
    "    \n",
    "    return -1\n",
    "\n",
    "# Text\n",
    "text = \"ABAAABCD\"\n",
    "# Pattern\n",
    "pattern = \"ABC\"\n",
    "\n",
    "# Call the boyer_moore_search function\n",
    "result = boyer_moore_search(text, pattern)\n",
    "\n",
    "if result != -1:\n",
    "    print(f\"Pattern found at index {result}.\")\n",
    "else:\n",
    "    print(\"Pattern not found in the text.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00e64b13-f9e6-409b-b1ec-8309dd5e60a6",
   "metadata": {},
   "source": [
    "Dalam kode di atas, fungsi bad_character_table membuat tabel \"bad character\" yang akan membantu dalam perhitungan langkah yang diperlukan jika terjadi ketidakcocokan karakter. Fungsi boyer_moore_search melakukan pencarian pola dalam teks menggunakan algoritma Boyer-Moore.\n",
    "\n",
    "Setelah menginisialisasi teks dan pola yang akan dicari, kita memanggil fungsi boyer_moore_search dan mencetak indeks di mana pola ditemukan dalam teks. Jika tidak ditemukan, pesan yang sesuai akan dicetak."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab565099-9e15-4abd-8c65-d83b85934f72",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def jump_search(arr, target):\n",
    "    n = len(arr)\n",
    "    step = int(math.sqrt(n))\n",
    "    prev = 0\n",
    "    \n",
    "    while arr[min(step, n)-1] < target:\n",
    "        prev = step\n",
    "        step += int(math.sqrt(n))\n",
    "        if prev >= n:\n",
    "            return -1\n",
    "    \n",
    "    while arr[prev] < target:\n",
    "        prev += 1\n",
    "        if prev == min(step, n):\n",
    "            return -1\n",
    "    \n",
    "    if arr[prev] == target:\n",
    "        return prev\n",
    "    return -1\n",
    "\n",
    "# Sorted array\n",
    "arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]\n",
    "# Target element\n",
    "target = 11\n",
    "\n",
    "# Call the jump_search function\n",
    "result = jump_search(arr, target)\n",
    "\n",
    "if result != -1:\n",
    "    print(f\"Element {target} found at index {result}.\")\n",
    "else:\n",
    "    print(f\"Element {target} not found in the array.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "979ff1a4-bb98-4205-a023-8f06fb8d84b3",
   "metadata": {},
   "source": [
    "Dalam kode di atas, fungsi jump_search melakukan pencarian elemen dalam rangkaian data terurut menggunakan algoritma Jump Search.\n",
    "\n",
    "Setelah menginisialisasi rangkaian data terurut dan elemen yang akan dicari, kita memanggil fungsi jump_search dan mencetak indeks di mana elemen ditemukan dalam rangkaian data. Jika tidak ditemukan, pesan yang sesuai akan dicetak."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51e03886-dfd6-42cc-b584-ca11dc79c414",
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(arr, left, right, target):\n",
    "    if right >= left:\n",
    "        mid = left + (right - left) // 2\n",
    "        if arr[mid] == target:\n",
    "            return mid\n",
    "        elif arr[mid] > target:\n",
    "            return binary_search(arr, left, mid - 1, target)\n",
    "        else:\n",
    "            return binary_search(arr, mid + 1, right, target)\n",
    "    return -1\n",
    "\n",
    "def exponential_search(arr, target):\n",
    "    n = len(arr)\n",
    "    if arr[0] == target:\n",
    "        return 0\n",
    "\n",
    "    i = 1\n",
    "    while i < n and arr[i] <= target:\n",
    "        i *= 2\n",
    "\n",
    "    return binary_search(arr, i // 2, min(i, n), target)\n",
    "\n",
    "# Sorted array\n",
    "arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]\n",
    "# Target element\n",
    "target = 11\n",
    "\n",
    "# Call the exponential_search function\n",
    "result = exponential_search(arr, target)\n",
    "\n",
    "if result != -1:\n",
    "    print(f\"Element {target} found at index {result}.\")\n",
    "else:\n",
    "    print(f\"Element {target} not found in the array.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8950d5c9-b705-4bf0-8d23-a31e7d0c8f8c",
   "metadata": {},
   "source": [
    "Dalam kode di atas, fungsi binary_search digunakan untuk melakukan pencarian biner dalam subarray tertentu. Fungsi exponential_search melakukan pencarian elemen dalam rangkaian data terurut menggunakan algoritma Exponential Search.\n",
    "\n",
    "Setelah menginisialisasi rangkaian data terurut dan elemen yang akan dicari, kita memanggil fungsi exponential_search dan mencetak indeks di mana elemen ditemukan dalam rangkaian data. Jika tidak ditemukan, pesan yang sesuai akan dicetak."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}