Читайте также:
|
Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Переменные lowerBound и upperBound содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением upperBound становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.
Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.
Алгоритм двоичного поиска приведен ниже:
lowerBound = 0
upperBound = size
Повторять бесконечно
M = (lowerBound + upperBound) / 2
Если K < A[M], то
upperBound = M – 1
Иначе Если K > A[M], то
lowerBound = M + 1
Иначе
Сообщить «Элемент найден, его индекс:», M
Выход из цикла
Все если
Если lowerBound > upperBound, то
Сообщить «Элемент не найден»
Выход из цикла
Все если
Все повторять
В описанном выше алгоритме приняты следующие условия:
1. size – размер массива
2. K – число, которое нужно найти
3. М – индекс найденного элемента.
Варианты индивидуальных заданий
| Задание | Сложность | Алгоритм сортировки | Алгоритм поиска | |
| 1. | элементы, присутствующие в обоих массивах А и В | Пузырьком | Линейный | |
| 2. | элементы, которые есть только в массиве А или только в массиве В | Пузырьком | Линейный | |
| 3. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Пузырьком | Линейный | |
| 4. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Пузырьком | Линейный | |
| 5. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Пузырьком | Линейный | |
| 6. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Пузырьком | Линейный | |
| 7. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Пузырьком | Линейный | |
| 8. | элементы массива А, повторяющиеся в массиве В несколько раз | Пузырьком | Линейный | |
| 9. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Пузырьком | Линейный | |
| 10. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Пузырьком | Линейный | |
| 11. | повторяющиеся элементы массива А, которые есть в массиве В | Пузырьком | Линейный | |
| 12. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Пузырьком | Линейный | |
| 13. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Пузырьком | Линейный | |
| 14. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Пузырьком | Линейный | |
| 15. | повторяющиеся элементы массива А, которых нет в массиве В | Пузырьком | Линейный | |
| 16. | элементы, присутствующие в обоих массивах А и В | Выбором | Линейный | |
| 17. | элементы, которые есть только в массиве А или только в массиве В | Выбором | Линейный | |
| 18. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Выбором | Линейный | |
| 19. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Выбором | Линейный | |
| 20. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Выбором | Линейный | |
| 21. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Выбором | Линейный | |
| 22. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Выбором | Линейный | |
| 23. | элементы массива А, повторяющиеся в массиве В несколько раз | Выбором | Линейный | |
| 24. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Выбором | Линейный | |
| 25. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Выбором | Линейный | |
| 26. | повторяющиеся элементы массива А, которые есть в массиве В | Выбором | Линейный | |
| 27. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Выбором | Линейный | |
| 28. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Выбором | Линейный | |
| 29. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Выбором | Линейный | |
| 30. | повторяющиеся элементы массива А, которых нет в массиве В | Выбором | Линейный | |
| 31. | элементы, присутствующие в обоих массивах А и В | Вставками | Линейный | |
| 32. | элементы, которые есть только в массиве А или только в массиве В | Вставками | Линейный | |
| 33. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Вставками | Линейный | |
| 34. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Вставками | Линейный | |
| 35. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Вставками | Линейный | |
| 36. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Вставками | Линейный | |
| 37. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Вставками | Линейный | |
| 38. | элементы массива А, повторяющиеся в массиве В несколько раз | Вставками | Линейный | |
| 39. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Вставками | Линейный | |
| 40. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Вставками | Линейный | |
| 41. | повторяющиеся элементы массива А, которые есть в массиве В | Вставками | Линейный | |
| 42. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Вставками | Линейный | |
| 43. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Вставками | Линейный | |
| 44. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Вставками | Линейный | |
| 45. | повторяющиеся элементы массива А, которых нет в массиве В | Вставками | Линейный | |
| 46. | элементы, присутствующие в обоих массивах А и В | Подсчетом | Линейный | |
| 47. | элементы, которые есть только в массиве А или только в массиве В | Подсчетом | Линейный | |
| 48. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Подсчетом | Линейный | |
| 49. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Подсчетом | Линейный | |
| 50. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Подсчетом | Линейный | |
| 51. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Подсчетом | Линейный | |
| 52. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Подсчетом | Линейный | |
| 53. | элементы массива А, повторяющиеся в массиве В несколько раз | Подсчетом | Линейный | |
| 54. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Подсчетом | Линейный | |
| 55. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Подсчетом | Линейный | |
| 56. | повторяющиеся элементы массива А, которые есть в массиве В | Подсчетом | Линейный | |
| 57. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Подсчетом | Линейный | |
| 58. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Подсчетом | Линейный | |
| 59. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Подсчетом | Линейный | |
| 60. | повторяющиеся элементы массива А, которых нет в массиве В | Подсчетом | Линейный | |
| 61. | элементы, присутствующие в обоих массивах А и В | Пузырьком | Двоичный | |
| 62. | элементы, которые есть только в массиве А или только в массиве В | Пузырьком | Двоичный | |
| 63. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Пузырьком | Двоичный | |
| 64. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Пузырьком | Двоичный | |
| 65. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Пузырьком | Двоичный | |
| 66. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Пузырьком | Двоичный | |
| 67. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Пузырьком | Двоичный | |
| 68. | элементы массива А, повторяющиеся в массиве В несколько раз | Пузырьком | Двоичный | |
| 69. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Пузырьком | Двоичный | |
| 70. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Пузырьком | Двоичный | |
| 71. | повторяющиеся элементы массива А, которые есть в массиве В | Пузырьком | Двоичный | |
| 72. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Пузырьком | Двоичный | |
| 73. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Пузырьком | Двоичный | |
| 74. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Пузырьком | Двоичный | |
| 75. | повторяющиеся элементы массива А, которых нет в массиве В | Пузырьком | Двоичный | |
| 76. | элементы, присутствующие в обоих массивах А и В | Выбором | Двоичный | |
| 77. | элементы, которые есть только в массиве А или только в массиве В | Выбором | Двоичный | |
| 78. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Выбором | Двоичный | |
| 79. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Выбором | Двоичный | |
| 80. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Выбором | Двоичный | |
| 81. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Выбором | Двоичный | |
| 82. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Выбором | Двоичный | |
| 83. | элементы массива А, повторяющиеся в массиве В несколько раз | Выбором | Двоичный | |
| 84. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Выбором | Двоичный | |
| 85. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Выбором | Двоичный | |
| 86. | повторяющиеся элементы массива А, которые есть в массиве В | Выбором | Двоичный | |
| 87. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Выбором | Двоичный | |
| 88. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Выбором | Двоичный | |
| 89. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Выбором | Двоичный | |
| 90. | повторяющиеся элементы массива А, которых нет в массиве В | Выбором | Двоичный | |
| 91. | элементы, присутствующие в обоих массивах А и В | Вставками | Двоичный | |
| 92. | элементы, которые есть только в массиве А или только в массиве В | Вставками | Двоичный | |
| 93. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Вставками | Двоичный | |
| 94. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Вставками | Двоичный | |
| 95. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Вставками | Двоичный | |
| 96. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Вставками | Двоичный | |
| 97. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Вставками | Двоичный | |
| 98. | элементы массива А, повторяющиеся в массиве В несколько раз | Вставками | Двоичный | |
| 99. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Вставками | Двоичный | |
| 100. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Вставками | Двоичный | |
| 101. | повторяющиеся элементы массива А, которые есть в массиве В | Вставками | Двоичный | |
| 102. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Вставками | Двоичный | |
| 103. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Вставками | Двоичный | |
| 104. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Вставками | Двоичный | |
| 105. | повторяющиеся элементы массива А, которых нет в массиве В | Вставками | Двоичный | |
| 106. | элементы, присутствующие в обоих массивах А и В | Подсчетом | Двоичный | |
| 107. | элементы, которые есть только в массиве А или только в массиве В | Подсчетом | Двоичный | |
| 108. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Подсчетом | Двоичный | |
| 109. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Подсчетом | Двоичный | |
| 110. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Подсчетом | Двоичный | |
| 111. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Подсчетом | Двоичный | |
| 112. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Подсчетом | Двоичный | |
| 113. | элементы массива А, повторяющиеся в массиве В несколько раз | Подсчетом | Двоичный | |
| 114. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Подсчетом | Двоичный | |
| 115. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Подсчетом | Двоичный | |
| 116. | повторяющиеся элементы массива А, которые есть в массиве В | Подсчетом | Двоичный | |
| 117. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Подсчетом | Двоичный | |
| 118. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Подсчетом | Двоичный | |
| 119. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Подсчетом | Двоичный | |
| 120. | повторяющиеся элементы массива А, которых нет в массиве В | Подсчетом | Двоичный | |
| 121. | элементы, присутствующие в обоих массивах А и В | Слиянием | Линейный | |
| 122. | элементы, которые есть только в массиве А или только в массиве В | Слиянием | Линейный | |
| 123. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Слиянием | Линейный | |
| 124. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Слиянием | Линейный | |
| 125. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Слиянием | Линейный | |
| 126. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Слиянием | Линейный | |
| 127. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Слиянием | Линейный | |
| 128. | элементы массива А, повторяющиеся в массиве В несколько раз | Слиянием | Линейный | |
| 129. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Слиянием | Линейный | |
| 130. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Слиянием | Линейный | |
| 131. | повторяющиеся элементы массива А, которые есть в массиве В | Слиянием | Линейный | |
| 132. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Слиянием | Линейный | |
| 133. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Слиянием | Линейный | |
| 134. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Слиянием | Линейный | |
| 135. | повторяющиеся элементы массива А, которых нет в массиве В | Слиянием | Линейный | |
| 136. | элементы, присутствующие в обоих массивах А и В | Слиянием | Двоичный | |
| 137. | элементы, которые есть только в массиве А или только в массиве В | Слиянием | Двоичный | |
| 138. | элементы, которые присутствуют в массивеА, но отсутствуют в массиве В | Слиянием | Двоичный | |
| 139. | элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах | Слиянием | Двоичный | |
| 140. | элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В | Слиянием | Двоичный | |
| 141. | элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В | Слиянием | Двоичный | |
| 142. | элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) | Слиянием | Двоичный | |
| 143. | элементы массива А, повторяющиеся в массиве В несколько раз | Слиянием | Двоичный | |
| 144. | элементы присутствующие в обоих массивах А и В в одном экземпляре | Слиянием | Двоичный | |
| 145. | элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В | Слиянием | Двоичный | |
| 146. | повторяющиеся элементы массива А, которые есть в массиве В | Слиянием | Двоичный | |
| 147. | повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре | Слиянием | Двоичный | |
| 148. | неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах | Слиянием | Двоичный | |
| 149. | элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах | Слиянием | Двоичный | |
| 150. | повторяющиеся элементы массива А, которых нет в массиве В | Слиянием | Двоичный |
Дата добавления: 2015-07-11; просмотров: 123 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Сортировка вставками | | | Задание 1. Объявление и инициализация одномерных массивов. |