# Binary search (BST)

Поиск по массиву путем деления пополам.&#x20;

Для таблицы символов (Object in JS) строим BST. BST:

* У каждой ноды слева все элементы, кт. меньше и справа все элементы кт. больше
* Может быть сбалансированным, когда одинаковое кол-во листьев
* Может быть средне сбалансированным, когда элементы добавляются произвольно
* Может максимально несбалансированным&#x20;

**Проблематика**: может быть максимально несбалансированным, что в свою очередь устремляет добавление и поиск к O(N), вместо lgN. Соотв. сбалансированные деревья намного интереснее.

![](https://adrianmejia.com/images/balanced-vs-non-balanced-tree.jpg)

![](https://4251836425-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lnd5skvXnyJUQsGuNMc%2F-MjiGPDJwMymnoqKZ-Ul%2F-MjiGXZByWg6qWreH6e7%2Fimage.png?alt=media\&token=f9602a1f-aab7-4d2b-b9ab-7106e585a47e)
