2015-04-30
1003
Напишем функцию, которая реализует алгоритм бинарного поиска таким образом, чтобы при поиске элемента формировалась таблица значений переменных i, j, k и некоторых выражений так, как на рис. 7.1.
Рис. 7.1. Бинарный поиск. Таблица промежуточных значений
Текст функции хранится в листинге 7.5.
| Листинг 7.5. Поиск в упорядоченном массиве с таблицей промежуточных значений |
<html>
<head>
<title>Бинарный поиск. Таблица промежуточных значений</title>
<script language="JavaScript">
<!-- //
var v=new Array(2,3,5,6,6,7,10,11,20,25)
function testtab(obj,v,t)
{ var res="i j k v[k] t<= v[k]"+"\r\n"
var i=0
var j= v.length-1
var k
while (i < j)
{ k=Math.round((i+j)/2+0.5)-1
res = res + i + " "+j+" "+k+" "+"v[" + k + "]=" + v[k]+ " " + t + "<=" + v[k]+"\r\n"
if (t <= v[k])
j=k
else
i=k+1
}
res += "v[" + i + "]=" +v[i]+"\r\n"
obj.result1.value=res
if (v[i] == t)
{ return i}
else return -1
}
function test(obj)
{ obj.data1.value=v}
//-->
</script>
</head>
<body>
<h4>Реализация алгоритма бинарного поиска</h4>
<form name="form1">
<pre>
Массив: <input type="text" size=40 name="data1" ><hr>
Элемент: <input type="text" size=20 name="data2" ><<hr>
Результат поиска: <input type="text" size=20 name="result" ><hr>
Таблица промежуточных значений: <BR>
<textarea cols=50 rows=7 name="result1" > </textarea>
<input type="button" value=Определить onClick="test(form1); form1.result.value=testtab (form1,v,form1.data2.value)">
<input type="reset" value=Отменить>
</form>
</body>
</html>
