Модифицированный бинарный поиск

ДРУЗЬЯ, помогите, иначе отчислят.Написать программу.

Модифицированный бинарный поиск. Когда вам дают отсортированный массив, связанный список или матрицу и просят найти определённый элемент, лучшим алгоритмом будет бинарный поиск. Этот шаблон описывает эффективный способ решения всех задач, связанных с бинарным поиском.

Для набора по возрастанию шаблоны выглядят так:

1. Сначала найдите середину начала и конца. Простой способ найти середину был бы: middle = (start + end) / 2. Но от этого может быть целочисленное переполнение, поэтому рекомендуется представлять середину как: middle = start + (end — start) / 2.

2. Если ключ равен числу в середине индекса, верните середину.

3. Если «ключ» не равен середине индекса:

o Если ключ < arr [middle], уменьшите поиск до end = middle — 1.

o Если ключ > arr [middle], уменьшите поиск до to end = middle + 1.

Задачи, для которых подойдёт шаблон модифицированный бинарный поиск:

• Бинарный поиск, не зависящий от порядка (лёгкий);

• Поиск в отсортированном бесконечном массиве (средний).