[C#] Arrays - 11 задача


1
11.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

от ivaylo.kenov (30760 точки)


32

Решение:

http://pastebin.com/waLCb1L8

Обяснение:

Преди да почнем трябва да отбележим, че този алгоритъм трябва да се прилга само в/у сортирани масиви. Какво правя:

1. Създава ме си един метод ( Може и без отделен метод, но така е по-прегледно ) , който приема аргументи - сортирания масив, в който търсим и стойността ( ключа ) на елемента който търсим. Връщаната от него стойност показва индекса, на който се намира елемента или ако върне -1 означава, че няма такъв елемент в масива.

2. Каква е основната логика тук ? Ще се опитам да я обясня с пример.

Има една игричка, която се състой в това да се познае число в дадена рамка, да кажем 0 до 100, като този който си е намислил числото, при наш опит ни казва дали сме познали, дали числото се намира под това което сме казали ( по-мало ), дали над това което сме казали ( по - голямо ). Една игра протича така:

Намислено число: 80 в рамка 0 -100.

1ви опит - 50 -> по-голямо

2ри опит - 75 -> по-голямо

3ти опит - 87 -> по-малко

и т.н. -> винаги определяме дали числото е по-малко или по-голямо и делим дадения интревал 2 за да го стесним :)

Ето малко визулано обяснение:

BinSearch

И като цяло това е основата на алгоритъма. Разпишете си го на лист хартия за да видите, колко е лесен :)

Ето още един пример, като този е конкретно за имплементацията на алгоритъма в/у масив:

BinSearchOnArray


от Teodor92 (13062 точки)


0
Добро обяснение и добър пример! Евала! :)

от vlad_karamfilov (4595 точки)

0
Здрасти и поздравления от мен. При всичкия труд който си вложил ме е яд да ти пиша подобен коментар - че нещо не е в ред :/ Но за доброто на тези които им предстои да се сблъскат с тази задача, ще го споделя :) Все пак поста ти е 1 от първите и най-вероятно някой който има проблем ще го прочете и ще се опита да го разбере.
За това почвам по същество: Става въпрос за "визуалното обяснение". Индексите трябва започват от "0" и като цяло снимката трябва да я пооправиш - 2-рия ред изчезва 3-тия се запазва и накрая се добавя още 1 в който всички точки съвпадат => намираме ключа с съответния индекс.

от Assi.NET (3050 точки)



6

http://pastebin.com/8b2bPp6r

Куртев добре ви е обяснил алгоритъма на търсенето и с колегата Ивайло са дали итеративно решение. Аз ще се опитам да ви обесня рекурсивното решение

Като цяло то е същото като итеративното, само че без цикли.

Както вече разбрахме binary search работи само със сортирани масиви, така че правим сортирането извън метода, за да избегнем допълнително излишно сортиране, ако го сложим в метода.

За пример ще ползвам масива {1,2,3,4,5,6,7}.

Ключът към решението е средата и нейната манипулация. Тази манипулация става с тези min max, които има и в двете решения.

  • Когато търсеното число е по-голямо от числтото в средата(number>array[middleElement]) -> увеличаваме началото(минимума) на "подмасива"(от 4 става 5). Така намираме средата на подмасива по формулата (min+max)/2.

Тоест сега средата ни е: (4+6)/2=5. Където 4 и 6 са номерата на елементите(началото и края на подмасива). Тоест средата ни е числото 6.

  • Когато търсеното число е по-малко от числтото в средата(number<array[middleElement]) -> намаляваме края(максимума) на "подмасива"(от 4 става 3). Така намираме средата на подмасива по формулата (min+max)/2

Тоест сега средата ни е: (0+3)/2=1. Където 0 и 3 са номерата на елементите(началото и края на подмасива). Тоест средата ни е числото 2.

 

След това извършваме тези действия, докато средата ни е равна на числото,  в чиито случай сме намерили решение.

Ако началото стане по-голямо от края(което само по себе си няма логика) => няма такова число в масива.

Това извикване на метода сам от себе си(повторение на кода) се нарича рекурсия, а случаите в които рекурсията свършва(намерено е решение или няма такова), се нарича дъно на рекурсията и е изключително важно, за да не зависне машината или да не се препълни стека.

Допълнителни ресурси:

Рекурсия: 

http://www.introprogramming.info/intro-csharp-book/read-online/glava10-rekursiq/

http://www.youtube.com/watch?v=2GCmXfKhTLc

Методи:

http://www.introprogramming.info/intro-csharp-book/read-online/glava9-metodi/

http://www.youtube.com/watch?v=CEqY6_Fp5wQ (видеото е от 2009, но са важни принципите, ако искате това от 2012, пишете ми съобщение да ви го пратя)


от kirov (4821 точки)


5

Ето и моето решение: source.


от jasssonpet (6814 точки)


0
Язоне, искам да ми се падат твоите домашни за проверка :) Мисля, че ще ми отнема по 15 секунди на задача. Макар че, тук си прекалил с писането, можеше вместо int m = l + (r - l) / 2; да напишеш int m = l/2 + r/2; и да спестиш сума ти писане :)

от AntonPetrov (654 точки)

0
Може и (l + r) / 2, но така може да се получи препълване. Между другото този бъг е открит сравнително по-късно от измислянето на алгоритъма: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1

от jasssonpet (6814 точки)


1
Binary Search implementation:
http://pastebin.com/6kUsBNHn
В while цикъла условно разделям масива на 2 части като за целта използвам променлива middle, на която казвам да е равна на началния индекс на масива + крайния индекс на масива делено на 2. След това проверявам дали търсената стойност е по-голяма от тази в средата (намираща се на индекс arr[middle], ако да - то числата в масива, които са по-малки (съответно тези намиращи се вляво от нея) и стойността, намираща се на индекса, равен на middle не ми трябват повече и затова на долната граница min задавам стойност равна на middle (което се е оказало по-малко от търсената стойност) + 1 - т.е. новата стойност на middle е следващият подред по-голям индекс в масива. Обратно - ако търсената стойност е по-малка от тази в средата, по аналогичен начин игнорирам всички стойности, които са по-големи от средата - т.е намиращи се вдясно от нея, включително и самата среда, като на максималната граница задавам стойност равна на текущия индекс в стойността, която пази средата - middle - 1; Цялото това нещо се повтаря докато нито едното, нито другото условие са верни (т.е. търсената стойност е нито по-голяма, нито по-малка от стойността, пазена в middle). Тогава прекъсвам цикъла. След това проверявам. Ако стойността на middle e равна на търсената - отговорът е намерен, печатам го на конзолата. Ако не е равна - няма такава стойност в масива.

от anonymous (0 точки)


4

В блога си / http://elibk.wordpress.com/ / съм се опитала да представя подробно обяснение на алгоритъма. Надявам се да е от полза. :)

Edit: Така е, при който не си тества граничните случаи. Кодът е поправен. Статията ще бъде редактирана. Един съвет за по-недосетливите(като мен): трябва да си тествате граничните случаи,т.е първите и последните елементи. Колкото и яко да ви изглежда решението, нищо не струва, ако работи само понякога. Извинявам се, ако съм подвела някого и благодаря на колегата vstoyanov за открития бъг!!!

EDIT: Статията е редактирана!

 


от el_b_k (424 точки)


0
Здравей. При някои от числата (3,6,8...) ми излиза "Not fount in the array".

от vstoyanov (0 точки)

0
Благодаря! Намерих проблема. Статията е редактирана!

от el_b_k (424 точки)


1

http://pastebin.com/Q4Ji7Lgq

Това е моето решение и моля Ви да му хвърлите едно око и да кажете дали отговаря на условията?cheeky:


от ilv323 (803 точки)


0
ами идеята е не да ползваш функцията наготово, а ти да я напишеш. Иначе работи правилно.

от makmidov (598 точки)


1
Ето и моето решение,
http://pastebin.com/Aq0HHYSY
добавил съм обяснения и съм дал свобода на потребителя да си въвежда числата. Това е едно от нещата, което ме изненадва. Повечето решения не само на тази задача пропускат това и ако искам да тествам трябва да си дописвам код.

от makmidov (598 точки)


0
Не е задължително при някои задачи входът да се чете от конзолата.

от rnikiforova (1198 точки)


0
Решението ми: http://pastebin.com/5TZAfjQT

от werew (576 точки)


1
http://pastebin.com/tTA7EyPQ

от Rokata (397 точки)