# ST Using Binary search (ordered array)

Associative Array Abstraction

Associate one value with each key.

* Method <mark style="color:blue;">Search()</mark> throws an exception if the key is not present.&#x20;
* Method <mark style="color:blue;">put()</mark> overwrites old value with new value.

{% code title="Smbol Table.h" %}
```cpp
#pragma once
using namespace std;

template <typename Key, typename Value>
class ST
{
     Key *keys;
     Value *vals;
     int n;
     int elements = 0;
     int i = -1; // increment before insertion & decrement after deletion
     bool isEmpty();
     bool isFull();

public:
     ST(int);

     int size();
     void put(Key, Value);
     bool delPair(Key);

     bool deleteMin();
     bool deleteMax();

     void max();
     void min();

     bool contain(Key);

     Value get(Key);
     int rank(Key);

     void print();
     Key getKey(int) ;
};

template <typename Key, typename Value>
int ST<Key, Value>::size()
{
     return elements;
}

template <typename Key, typename Value>
Key ST<Key, Value>::getKey(int i)
{
     return keys[i];
}

template <typename Key, typename Value>
bool ST<Key, Value>::isEmpty()
{
     return elements == 0;
}

template <typename Key, typename Value>
bool ST<Key, Value>::isFull()
{
     return elements == n;
}

template <typename Key, typename Value>
ST<Key, Value>::ST(int n)
{
     this->n = n;
     keys = new Key[n];
     vals = new Value[n];
}

template <typename Key, typename Value>
void ST<Key, Value>::put(Key key, Value val)
{
     if (elements == 0)
     {
          i++;
          keys[i] = key;
          vals[i] = val;
          elements++;
          return;
     }
     int j = rank(key); // gives the index where to insert the new key & value or location of the key that's already present
     // if Key already in the table, jsut change its value
     if (j <= i && keys[j] == key)
     {
          vals[j] = val;
     }
     else
     {
          // resizing array
          if (isFull())
          {
               n = n * 2;
               Key *temp1 = new Key[n];
               Value *temp2 = new Value[n];
               for (int k = 0; k <= i; k++)
               {
                    temp1[k] = keys[k];
                    temp2[k] = vals[k];
               }
               keys = temp1;
               vals = temp2;
          }

          // first insert at the end
          i++;
          keys[i] = key;
          vals[i] = val;

          // second swap kth element with ith(Last) element until k < i
          for (int k = j; k < i; k++)
          {
               swap(keys[k], keys[i]);
               swap(vals[k], vals[i]);
          }

          // -- slide logic --
          // Key Ktemp = keys[j];
          // Value Vtemp = vals[j];
          // // Insert in the SORT order.
          // for (int k = j; k < i; k++)
          // {
          //      swap(Ktemp, keys[k + 1]);
          //      swap(Vtemp, vals[k + 1]);
          // }
          // i++;
          // keys[i] = Ktemp;
          // vals[i] = Vtemp;

          // inserting new key and value at its right location.
          // keys[j] = key;
          // vals[j] = val;
          elements++;
     }
}

template <typename Key, typename Value>
bool ST<Key, Value>::delPair(Key key)
{
     if (isEmpty())
          return false;
     if (keys[i] == key)
     {
          return deleteMax();
     }

     int delIndex = rank(key);
     if (keys[delIndex] == key)
     {
          // shifting one step backward or use the insertion logic
          for (int k = i; k > delIndex; k--)
          {
               swap(keys[delIndex], keys[k]);
               swap(vals[delIndex], vals[k]);
          }
          i--;
          elements--;
          return true;
     }
     return false;
}

template <typename Key, typename Value>
bool ST<Key, Value>::deleteMin()
{
     return delPair(keys[0]);
}

template <typename Key, typename Value>
bool ST<Key, Value>::deleteMax()
{
     if (isEmpty())
     {
          cout << "Empty symbol table" << endl;
          return false;
     }
     i--;
     elements--;
     return true;
}

template <typename Key, typename Value>
void ST<Key, Value>::max()
{
     if (isEmpty())
          cout << "Empty symbol table" << endl;
     cout << keys[i] << ":" << vals[i];
}

template <typename Key, typename Value>
void ST<Key, Value>::min()
{
     if (isEmpty())
          cout << "Empty symbol table" << endl;
     cout << keys[0] << ":" << vals[0];
}

template <typename Key, typename Value>
bool ST<Key, Value>::contain(Key key)
{
     int k = rank(key);
     return k <= i && keys[k] == key;
}

template <typename Key, typename Value>
Value ST<Key, Value>::get(Key key)
{
     if (isEmpty())
          throw runtime_error("Search operation on empty symbol table.");
     int k = rank(key);
     if (k <= i && keys[k] == key)
          return vals[k];
     else
          throw invalid_argument("Key not found in the symbol table.");
}

template <typename Key, typename Value>
int ST<Key, Value>::rank(Key key)
{
     int s = 0, e = i;
     while (s <= e)
     {
          int mid = s + (e - s) / 2;
          if (keys[mid] == key)
               return mid;
          else if (keys[mid] < key)
               s = mid + 1;
          else
               e = mid - 1;
     }
     return s;
}

template <typename Key, typename Value>
void ST<Key, Value>::print()
{
     for (int j = 0; j < elements; j++)
     {
          cout << keys[j] << " : " << vals[j] << endl;
     }
}
```
{% endcode %}

{% code title="main.cpp" %}
```cpp
#include <iostream>
#include "Symbol Table.h"

int main()
{
     try
     {
          // ST<string, int> *st = new ST<string, int>(5);
          // st->put("Banana", 0);
          // st->put("Aapple", 1);
          // st->put("Apple", 2);
          // cout << (boolalpha) << st->delPair("Apple") << endl;

          ST<char, int> *st = new ST<char, int>(5);
          st->put('S', 0);
          st->put('E', 1);
          st->put('A', 2);
          st->put('R', 3);
          st->put('C', 4);
          st->put('H', 5);
          st->put('E', 6);
          st->put('X', 7);
          st->put('A', 8);
          st->put('M', 9);
          st->put('P', 10);
          st->put('L', 11);
          st->put('E', 12);
          cout << (boolalpha) << st->delPair('X') << endl;
          cout << (boolalpha) << st->contain('X') << endl;

          st->deleteMin();
          st->print();
          cout << "Value At Key: " << st->get('A') << endl;
          delete st;
     }
     catch (const runtime_error &e)
     {
          cerr << "Runtime error: " << e.what() << endl; // cerr is the standard error stream, typically used for error messages and diagnostics.
     }
     catch (const invalid_argument &e)
     {
          cerr << "Invalid argument: " << e.what() << endl;
     }
     catch (...)
     {
          cerr << "An unexpected error occurred." << endl;
     }
}
```
{% endcode %}

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FD1eLTxD4cNeGqI5VB1KR%2Fimage.png?alt=media&#x26;token=e2f63978-442c-42f2-934f-018066656eac" alt=""><figcaption></figcaption></figure>

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2F6OfZD5GPJmWqdF2M0d3G%2Fimage.png?alt=media&#x26;token=17c5bc96-1864-4f72-9563-dc2f4548250e" alt=""><figcaption></figcaption></figure>
