[JS] Arrays - зад. 7


3

Някой реши ли вече  тази задача? 

 

7.*Write a program that finds the index of given element in a sorted array of integers by using the binary search algorithm (find it in Wikipedia).



Отговори



11
Да. Алгоритъмът е следния:
1. Сортираш масива във възходящ ред;
2. Взимаш средния елемент на масива - ако той съвпада с търсения елемент значи си го намерила;
3. Ако не съвпада:
а.) ако средния елемент е по-голям от търсения елемент взимаш лявата половина на масива и гледаш нейния среден елемент;
б.) ако средния елемент е по-малък от търсения елемент, взимаш дясната половина на масива и гледаш нейния среден елемент;
4. По този начин на всяка итерация от цикъла намаляваш диапазона на търсене наполовина. Ако дължината на диапазона на търсене стане нула, значи търсения елемент не е намерен.

от bakalov85 (604 точки)


1

Тук е описано по-подробно, ако ти се навлиза в материята:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch


от venelinpetrov (1221 точки)


0
Благодаря за обяснението, но аз алгоритъма го разбрах, имах проблем с извеждането на позицията на елемента, ако бъде намерен такъв в масива. Вече го направих.
Как извеждате резултата при тези задачки? document.write(); ?



0
Лично аз извеждам резултата с document.write(); но може да го извеждаш и в конзолата чрез console.log();

от georgi.s.yankov (6219 точки)

0
Аз не мога да изведа резултата ...

от ilgeo (115 точки)



5

Предлагам ви да изгледате едно интересно 6-минутно видео, на което добре и нагледно се обяснява какво представлява алгоритъма "binary search", както и неговите предимства пред "linear search".

Заповядайте: Linear and Binary Searching.

Ако някой от вас се е отказал да прави тази задачка само да обърна внимание, че половината от задачата я имате готова, ако сте стигнали до тази. Имам предвид, че за да решите 7 зад. е необходимо решението на 5 зад. + "binary search".

Същото важи и за 6 зад., която пък само обединява решенията на двете задачи (зад. 3 и зад. 5) и донагласяте. Аз поне така съм го направил.

Дано съм ви бил полезен!


от georgi.s.yankov (6219 точки)


0
В този ред на мисли задача 6 ми излезе 3 реда без да преувеличавам.

от venelinpetrov (1221 точки)

0
Благодаря за споделеното!+:)

от svetlaz (269 точки)



1
А ако имаме два елемента, отговарящи на изискванията, какъв е отговора? Какъв индекс е елемента? А какво става, когато имаме масив 1,2,3,4,4,4,5,6,7 и питаме за индекса на елемента 4? Според този алгоритъм индексът е [4], но имаме още 2 правилни отговора, като те са в двете половини на масива.



0
Когато се търси индексът на дадена стойност в масива, значи се търси в масив, в който не се повтарят стойностите. Ако се търсеше в такъв масив с повтарящи се стойности, това е друга задача. Например намерете колко пъти се повтаря числото 4 и къде :-)

от ilgeo (115 точки)


3

Понеже задачите за домашно по JavaScript Part1 на курсистите започнали курса на 18.02.2013 съвпадат с тези, ще пусна моето решение тук, за да избегна дублирането на теми.

Demo

Source

Имаме зададен по условие сортиран масив, който е видим за потребителя. Следва въвеждане от потребителя на произволен елемент от масива в text box-a, за който посредством Binary Search algorithm трябва да открием неговият индекс. След прочитане на стойността на text-box-a по ID, правим и първата проверка- ако въведеният вход е NaN, то подканваме потребителя да въведе отново коректна стойност за вход. Ако това е в сила си въвеждаме променливи, който ще пазят долната и съответно горната граница на интервала, в който ще търсим интересуващото ни число- в случая нашите граници се явяват и границите на масива. Посредством друга променлива на име half взимаме средният елемент на масива. Ако това е и елемента който е зададен от потребителя, то търсенето приключва и извеждаме индексът му на екрана. Ако не е, проверяваме дали числото е по-голямо или по-малко от това, на което търсим индекса. Ако е по-малко, взимаме дясната половина на масива и отново "разполовяваме" докато не открием търсеното от нас число. Аналогична е ситуацията ако е по-голямо с тази разлика, че разглеждаме лявата половина. Идеята е, че така с няколко стъпки разполовявайки интервала за търсене ние достигаме до търсеният от нас индекс на елемент от масива.


от Vlado_XXX (944 точки)


0

Toва е моят код: http://pastebin.com/wZdhR8Mt

но не мога да разбера, защо не работи цикъла? Изкарва ми "undefined" като стойност на index. А на всичкото от горе, ако сложа parseInt на mid = (min + max)/2; и програмата забива и казва, че има грешен скрипт...


от Mitko_Mitev (1276 точки)


0
ето кода ти с леки модификации, ползвала съм булевата променлива, защото без такъв флаг мисля че се влиза в безкраен цикъл

от pdrenovska (2196 точки)


0

Не мога да разбера нещо. Защо на 7-ма задача, а също и на 5-та, като въведа някакви стойности по-големи от трицифрени числа и те се лепват за съответното им едноцифрено. Т. е. Ако имам в масива 5, 6, 2, 4, 7, 65974, 2546465, то при подредбата ми ги изкарва по следния начин: 2, 2546465, 4, 5, 6, 65974, 7. Къде е грешката, какво пропускам?


от pe6eto (222 точки)


0
Прегледай лекцията... Вградения сорт ги сравнява като стрингове (лексикографски) и стринга "222" е преди стринга "7" .. Можеш да ги сортираш ръчно (да имплементираш сортиращ алгоритъм) или да използваш вградения сорт като му подадеш функция, по която да сравнява: arrayName.sort(SortFunc); SortFunc(a,b) { return (a==b) ? 0 : a>b ? 1 : -1 } Ако не разбираш последната функция казвай да я обяснявам ;)

от westi3m (5621 точки)


1

Хайде и аз

 

function binarySearch(arr, key){
  var min = 0;
  var max = arr.length - 1;
  var found = false;
  var mid;
  var returnIndex = -1;
  
  while (!found && min <= max) {
    mid = parseInt((min + max) / 2, 10);
    if (arr[mid] == key) {
      returnIndex = mid;
      found = true;
    }
    else if (arr[mid] < key) {
      min = mid + 1;
    }
    else {
      max = mid - 1;
    }
  }
  return returnIndex;
 

от ybachev (144 точки)


1
Ето и моето решение. Сложил съм "console.log" на няколко места за да стане по нагледано. Само последния е задължителен, останалите може да се изтрият.
http://jsbin.com/EtAyirU/2/edit?html,console

от bstaykov (528 точки)