· x сравнивается со средним элементом массива.
· Индекс среднего элемента i = (i1+i2)/2, где i1 = 0, i2 = n – 1.
· Если x = a(i), задача решена.
· Если x<a(i), то поиск продолжается в левой половине:
i2 = i – 1, i1 не изменяется.
· Если x>a(i), то поиск продолжается в правой половине:
i1 = i + 1, i2 не изменяется.
· Искомый элемент отсутствует в массиве, если выполнится условие i2<i1.
Реализовать алгоритм самостоятельно.
12. Объединение двух массивов с чередованием элементов.
Требуется объединить два массива одинакового размера A = (a0, a1, …, an–1 ) и B = (b0, b1, …, bn–1) в один массив C = (a0, b0, a1, b1,…, an–1, bn–1).
Элементами массива С с четными индексами являются элементы массива A:
c0 = a0; с2 = a1; …; с2i = ai, …,
элементами с нечетными индексами – элементы массива B:
c1 = b0, c3 = b1…, … , с2i–1 = bi,…
Таким образом, требуется организовать цикл и выполнить операции
с2i= ai, с2i–1 = bi – 1, для i = 0, 1, 2, , n – 1.
Если массивы имеют разные размеры, то больший массив обрезается по размеру меньшего и меньший массив и урезанный большой объединяются в соответствии с предложенным алгоритмом. Далее оставшиеся элементы большего массива пересылаются подряд.
13. Объединение двух упорядоченных массивов в один с сохранением упорядоченности.
Требуется объединить два упорядоченных по убыванию массива A размером n и B размера m в один массив C размером n + m, также упорядоченный.
