2015-04-30
1375
Напишите функцию, определяющую, есть ли заданный элемент в упорядоченном массиве.
Если элементы массива упорядочены, то организовать поиск элемента с заданным значением можно согласно алгоритму бинарного поиска. Пусть переменная i - индекс левого элемента, значение j - индекс правого элемента, для элементов массива, среди которых осуществляется поиск. Определяется индекс элемента k, находящегося посередине. Далее k-ый элемент массива v[k] сравнивается с образцом t. Если окажется, что t <= v[k], то поиск следует продолжать среди элементов с индексами [i,k]., если же t > v[k], искать надо среди элементов [k+1,j]. Процесс поиска продолжается до тех пор, пока исследуемая часть массива не станет равной одному элементу, тогда результат будет зависеть от того, равен этот элемент образцу или нет. Функцию binsear(v,t) представлена в листинге 7.4.
| Листинг 7.4. Поиск элемента в упорядоченном массиве |
function binsear (v,t)
{ var i=0
var j= v.length-1
var k
while (i < j)
{ k=Math.round((i+j)/2+0.5)-1
if (t <= v[k])
j=k
else
i=k+1
}
if (v[i] == t) { return i}
else return -1
}
Заметим, что значение переменной i может только увеличиваться, значение переменной j только уменьшаться, причем при каждом повторении тела цикла либо увеличивается значение переменной i, либо уменьшается значение переменной j и значение переменной i меньше значения j. Когда значения i и j совпадут, цикл завершит работу. Рассмотрим случай, когда исследуются только два элемента. Значение k на следующем шаге итерации станет равным значению i. Если значение t меньше или равно v[i], то переменной j будет присвоено значение k, значения переменных i и j совпадут, цикл завершит работу. Если же значение t более v[i], то переменной i присвоится значение k+1, и в этом случае значения i и j совпадут.
|
|
|
После выполнения цикла сравнивается значение i-того элемента со значением t, и результат выдается в качестве работы функции. Пусть исходный массив состоит из элементов, упорядоченных по возрастанию: 2,3,5,6,6,7,10,11,20,25. Пусть значение t равно 7. Ожидаемый результат - индекс найденного элемента, значение 5.
