{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7b2aea0a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class VetorOrdenado:\n",
    "    def __init__(self, capacidade):\n",
    "        self.capacidade = capacidade\n",
    "        self.ultima_posicao = -1\n",
    "        self.valores = [0] * capacidade\n",
    "\n",
    "    def imprimir(self):\n",
    "        # Imprime todos os elementos do vetor até a última posição ocupada\n",
    "        for i in range(self.ultima_posicao + 1):\n",
    "            print(self.valores[i], end=' | ')\n",
    "        print()\n",
    "\n",
    "    def inserir(self, valor):\n",
    "        # Verifica se o vetor está cheio, se estiver, imprime uma mensagem e não insere o valor\n",
    "        if self.ultima_posicao == self.capacidade - 1:\n",
    "            return print(\"Vetor cheio\")\n",
    "\n",
    "        # Inicializa a posição onde o novo valor será inserido em 0\n",
    "        posicao = 0\n",
    "        # Enquanto a posição for menor ou igual à última posição e o valor na posição for menor que o valor a ser inserido, incrementa a posição\n",
    "        while posicao <= self.ultima_posicao and self.valores[posicao] < valor:\n",
    "            posicao += 1\n",
    "\n",
    "        # Deslocar os elementos para a direita para abrir espaço para o novo valor\n",
    "        for i in range(self.ultima_posicao, posicao - 1, -1):\n",
    "            self.valores[i + 1] = self.valores[i]\n",
    "\n",
    "        # Inserir o valor na posição correta\n",
    "        self.valores[posicao] = valor\n",
    "        # Incrementar a última posição\n",
    "        self.ultima_posicao += 1\n",
    "\n",
    "    def pesquisa_linear(self, valor):\n",
    "        for i in range(self.ultima_posicao + 1):\n",
    "            if self.valores[i] == valor:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "    def pesquisa_binaria(self, valor):\n",
    "        inicio = 0\n",
    "        fim = self.ultima_posicao\n",
    "\n",
    "        while inicio <= fim:\n",
    "            meio = (inicio + fim) // 2\n",
    "            if self.valores[meio] == valor:\n",
    "                return meio\n",
    "            elif self.valores[meio] < valor:\n",
    "                inicio = meio + 1\n",
    "            else:\n",
    "                fim = meio - 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "    def remover(self, valor):\n",
    "        posicao = self.pesquisa_binaria(valor)\n",
    "        if posicao == -1:\n",
    "            return -1\n",
    "\n",
    "        for i in range(posicao, self.ultima_posicao):\n",
    "            self.valores[i] = self.valores[i + 1]\n",
    "\n",
    "        self.ultima_posicao -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "a91633fb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 | 20 | 30 | 40 | 50 | \n",
      "Pesquisa Linear de 20: 1\n",
      "Pesquisa Binária de 50: 4\n",
      "10 | 20 | 40 | 50 | \n",
      "20 | 40 | 50 | \n"
     ]
    }
   ],
   "source": [
    "vetor = VetorOrdenado(5)\n",
    "\n",
    "vetor.inserir(30)\n",
    "vetor.inserir(10)\n",
    "vetor.inserir(40)\n",
    "vetor.inserir(20)\n",
    "vetor.inserir(50)\n",
    "\n",
    "vetor.imprimir()\n",
    "\n",
    "print(\"Pesquisa Linear de 20:\", vetor.pesquisa_linear(20))\n",
    "print(\"Pesquisa Binária de 50:\", vetor.pesquisa_binaria(50))\n",
    "\n",
    "vetor.remover(30)\n",
    "vetor.imprimir()\n",
    "\n",
    "vetor.remover(10)\n",
    "vetor.imprimir()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01685fb1",
   "metadata": {},
   "source": [
    "Vetor Original: [10, 20, 30, 40, 50]\n",
    "\n",
    "Pesquisa Binária para o valor 50:\n",
    "\n",
    "| Passo | Início | Fim | Meio | Valor do Meio | Comparação |\n",
    "|---|---|---|---|---|---|\n",
    "| 1 | 0 | 4 | 2 | 30 | 50 > 30, procurar à direita |\n",
    "| 2 | 3 | 4 | 3 | 40 | 50 > 40, procurar à direita |\n",
    "| 3 | 4 | 4 | 4 | 50 | Valor encontrado! |\n",
    "\n",
    "Pesquisa Linear para o valor 50:\n",
    "\n",
    "| Passo | Índice | Valor | Comparação |\n",
    "|---|---|---|---|\n",
    "| 1 | 0 | 10 | 50 != 10 |\n",
    "| 2 | 1 | 20 | 50 != 20 |\n",
    "| 3 | 2 | 30 | 50 != 30 |\n",
    "| 4 | 3 | 40 | 50 != 40 |\n",
    "| 5 | 4 | 50 | Valor encontrado! |\n",
    "\n",
    "Pesquisa Binária para o valor 25 (não presente):\n",
    "\n",
    "| Passo | Início | Fim | Meio | Valor do Meio | Comparação |\n",
    "| ---|---|---|---|---|---|\n",
    "| 1 | 0 | 4 | 2 | 30 | 25 < 30, procurar à esquerda |\n",
    "| 2 | 0 | 1 | 0 | 10 | 25 > 10, procurar à direita |\n",
    "| 3 | 1 | 1 | 1 | 20 | 25 > 20, procurar à direita |\n",
    "\n",
    "Resultado: Valor não encontrado.\n",
    "\n",
    "Pesquisa Linear para o valor 25 (não presente):\n",
    "| Passo | Índice | Valor | Comparação |\n",
    "| ---|---|---|---|\n",
    "| 1 | 0 | 10 | 25 != 10 |\n",
    "| 2 | 1 | 20 | 25 != 20 |\n",
    "| 3 | 2 | 30 | 25 != 30 |\n",
    "| 4 | 3 | 40 | 25 != 40 |\n",
    "| 5 | 4 | 50 | 25 != 50 |\n",
    "\n",
    "Resultado: Valor não encontrado.\n",
    "\n",
    "Pesquisa Binária para o valor 30:\n",
    "| Passo | Início | Fim | Meio | Valor do Meio | Comparação |\n",
    "|---|---|---|---|---|---|\n",
    "| 1 | 0 | 4 | 2 | 30 | Valor encontrado! |\n",
    "\n",
    "Pesquisa Binária para o valor 10:\n",
    "| Passo | Início | Fim | Meio | Valor do Meio | Comparação |\n",
    "|---|---|---|---|---|---|\n",
    "| 1 | 0 | 4 | 2 | 30 | 10 < 30, procurar à esquerda |\n",
    "| 2 | 0 | 1 | 0 | 10 | Valor encontrado! |\n",
    "\n",
    "Pesquisa Linear para o valor 10:\n",
    "| Passo | Índice | Valor | Comparação |\n",
    "|---|---|---|---|\n",
    "| 1 | 0 | 10 | Valor encontrado! |\n"
   ]
  }
 ],
 "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.13.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}