[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).



Отговори



0

Решение

Сравнявам търсената стойност с средата на масива. Ако е по-малка - местя десния край на масива в средата. Ако е по-голяма - левия край на масива става средата. Ако не - значи съм намерил индекса на търсения елемент.


от dzhenko (3893 точки)


1
http://pastebin.com/65TN5MUd
Накратко - решението е стандартно според описанието за имплементация на метода binary searc! Искам само да обърна внимание на един ред от кода:
middle = parseInt((startSearch + endSearch)/2);
Не го бях забелязал и просто бях написал middle = (startSearch + endSearch)/2.
И браузърът блокира:) Около 1 час не бях забелязал къде е проблема...ако на някой му се случи да знае!



0
Да и при мен се случи ,но като го дебъгнеш и бързо се вижда,че е float ,а не int . Слагаш накрая едно |0 и вече е int .

от Veni.Naydenov (200 точки)


1

Ето и едно решение от мен. Това е само алгоритъма, по-нагоре са създадени всички променливи и масива е сортиран:

 

while (minIndex <= maxIndex) {
       currentIndex = parseInt((minIndex + maxIndex) / 2);
 
       if (array[currentIndex] < element) {
           minIndex++;
       }
       else if (array[currentIndex] > element) {
           maxIndex--;
       }
       else if (array[currentIndex] == element) {
           arrayIndexes += currentIndex + " ";
           var increasingIndex = currentIndex;
           var decreasingIndex = currentIndex;
           
           if (array[increasingIndex + 1] == element) {
               increasingIndex++;
 
               while (array[increasingIndex] == element) {
                   arrayIndexes += increasingIndex + " ";
                   increasingIndex++;
               }
           }
           if (array[currentIndex - 1] == element) {
               decreasingIndex--;
 
               while (array[decreasingIndex] == element) {
                   arrayIndexes += decreasingIndex + " ";
                   decreasingIndex--;
               }
           }
 
           break;
       }
       output = -1;
   }

 

 Самия алгоритъм binary search беше елементарен. Но ми отне почти час да измисля, как да покажа индексите на ВСИЧКИ срещания на елемента. Т.е. ако елемента се среща повече от веднъж в масива. 

 Идеята ми е да вкарам в отделен масив индексите на срещанията на елемента. 

 Когато binarey search срещне елемента, се включва един цикъл който да провери дали елементите след него са му равни. После нов цикъл за елементите преди него. И двата цикъла въртят докато срещнат различен елемент. 


от ivan.mihov1 (4988 точки)


0

Ето и моя вариант. 
Самият масив и номерът, чийто индекс се проверява, се взимат от <input> таговете. Мъчих се с часове докато установя, че за да работи правилно, трябва да парсна номера от втория <input>...иначе проверяваше само едната половина от масива, а ако внеса число от другата половина ми забиваше браузъра или пък само при две от числата ми връщаше "undefined" и още много други странни поведения, които ме озадачават...

http://pastebin.com/ffAJh17J


от Rub (0 точки)


0
Здравейте,
След няколко часа борба и аз успях да стигна до решение на задачата за имплементиране на двоичното търсене.
Изисквам въвеждане от страна на потребителя на масива и числото, което ще търси. След това сортирам масива и прилагам алгоритъма за двоично търсене чрез делене на "интервалите за търсене" (лява и дясна част) наполовина.
Накрая извеждам съобщение в зависимост от резултата.
http://pastebin.com/aVyC5vmr
Поздрави!

от kalina_sf (192 точки)


2

За мен най-интересното в тази задача беше, че има поне 6 начина да се намери средния елемент, т.е. да се изрази това, което на C# се прави с целочислено делене: 

C#:     mid = (high + low) / 2;

JavaScript:

mid = Math.floor((high + low) / 2);
mid = ~~((high + low) / 2);
mid = ((high + low) / 2) | 0;
mid = (high + low) >> 1;
mid = (high + low) >>> 1;
mid = parseInt((high + low) / 2);

 

За по-подробна дискусия може да погледнете тук: Integer division in JavaScript


от neutrino (3376 точки)


1

Здравейте, това е решението ми на задачата

Задача 7

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


от KaloyanBobev (330 точки)