Линейный и двоичный поиск элементов в массиве

Очень часто требуется найти в массиве заданное значение или сообщить, что его там нет. Для этого нужно просмотреть все элементы массива с первого до последнего. Как только будет найден элемент, равный заданному значению X, надо завершить поиск и вывести результат. Такой алгоритм называется линейным 

Линейный алгоритм используют для поиска максимального (минимального) элемента массива. Это тоже алгоритм поиска. Но здесь мы вынуждены идти до конца массива, т.к. необходимо сравнивать все элементы, с текущим значением максимума (минимума) и в случае если текущий элемент больше (меньше) значения максимума (минимума) заменять значение максимума (минимума). Эти алгоритмы рассматривали в более ранних курсах. 

Первое задание на реализацию данного алгоритма 

Алгоритм поиска заданного значения:
 
Для того, чтобы найти элемент равный заданному значению X необходимо просмотреть все элементы массива с первого до последнего.
 Как только будет найден элемент, равный заданному значени. Х, надо завершить поиск и вывести результат.

Проще всего этот алгорим реализовать с помощью оператора цикла while. 
Попробуйте сами добавить условие в операторе while

Попробуйте исправить задачу из предыдущего задания, чтобы она верно работала, даже если в массиве нет требуемого элемента. 
Подсказка: если требуемого элемента в массиве нет, то необходимо выйти из цикла как только произойдет выход за границу массива

PS
Нужно помнить, что в языке С++ (как и в языке Python, JavaScript, PHP) при использовании логической связки И (&&), если первая часть ложна, то вторая часть не проверяется
Например:
условие a=0 && b!=0
при a=5, первая часть а=0 - ложна, поэтому вторая часть b!=0 не будет проверяться компилятором.

Возможен еще один подход к решению этой задачи. Можно использовать досрочный выход из цикла, если найдено требуемое значение. 
В С++ для досрочного выхода из цикла используется оператор break;

Двоичный (или бинарный) поиск является эффективным алгоритмом поиска, выполняется он быстрее чем линейный поиск. Например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
 
Недостатками такого алгоритма является требование упорядоченности данных, а также возможности доступа к любому элементу данных за постоянное (не зависящее от количества данных) время. Таким образом алгоритм не может работать на неупорядоченных массивах.

Алгоритм
1.Выбрать средний элемент A[c] и сравнить с X.
2.Если X = A[c], то нашли (стоп).
3.Если X < A[c], искать дальше в первой половине.
4.Если X > A[c], искать дальше во второй половине.

Реализация




где:
А - исходный массив,
N - размер массива,
X - искомое число,

Возможны и другие реализации
Например, с использованием досрочного выхода из цикла

Сравнение алгоритмов линейного и двоичного поиска по числу сравнений
 
N линейный поиск двоичный поиск
2 2 2
16 16 5
1024 1024 11
1048576 1048576 21

Плюсы двоичной сортировки в том, что выполняется она быстрее.
Минусы - необходим предварительно отсортированный массив