[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

Ето и моето решение, направено чрез рекурсия. Съвпадащото число и масива се въвеждат през конзолата: 

http://pastebin.com/hTtxpsp4

Малко извън задачата искам да обърна внимание че когато дойде момента да оценяваме задачите на други колеги трябва да обръщаме голямо внимание на това какво точно се търси по условието и да не бързаме да пишем 2ки :) . Мисълта ми е следната - за пример в тази задача ако въведем че търсим числото 5 в масива 1,5,3,4,2. Тук индекса на търсеното число е 1, но след като го сортираме във възходящ ред той става 1,2,3,4,5(индекса на търсеното число вече е 4 и това е нещото което се търси в задачата).

 




0

Оставил съм коментарите от Уикипедията. Добавил съм едно "Иф" че за "Ненамерено" число накрая. С "While" цикъл някък си ми е по - разбираемо.  Обясненията на колегите Куртев и Киров са предостатъчни  +1 за двамата.

Ето го: http://pastebin.com/NPv5iCnd


от simonses (30 точки)


0
Това е моето решение - http://pastebin.com/1LyzM8wK
Умишлено използвам предварително въведен и сортиран масив. В два цикъла (while и for) проверявам за търсената стойност, като разделям предварително масива на две и проверявам дали търсената стойност е по-малка от последната стойност в лявата половина. Ако е така - продължавам търсенето във for цикъл за индекса на търсената стойност. Ако търсената стойност е по-голяма от последната стойност в лявата половина - продължавам търсенето във for цикъл за индекса на търсената стойност в дясната половина. Ако не я намеря, разделям тази половина в която последно съм търсил на две и се повтаря проверката отново. Ако намеря елемент със стойност равен на търсеният, програмата печати индекса и излиза, в противен случай издава съобщение за ненамерен индекс или грешно въведена стойност за масива.

от szaekov (155 точки)


0
http://pastebin.com/u1sM4ExZ



0
http://pastebin.com/auwUTJua

от sirjordan (67 точки)


1

Моето решение. Авторско.

Binary Search


от zhelyazkovn (2949 точки)


0

Ето 1 и от мен, но мисля че не съм го направила точно както трябва въпреки че работи.
http://pastebin.com/teUDWm9r


от Martichka (90 точки)


0
идеята НЕ е да проверяваш всеки елемент по отделно, защото ако имаш 1 000 001 елемента и търсиш 1 000 000 - я ще е доста бавно. Колегите по горе са обяснили каква е целта.

от makmidov (598 точки)

0
true четох че ефективността стига в най-лошия случай за 1 милион - 20 итерации :))

от ludmil.d (490 точки)


0
Решението ми е следното :
http://pastebin.com/Yhik4Ae6
Но неменуемо в мен се пробужда въпроса какво да направим при вариянт примерно, че числата от масива са подредени, но примерно през 2 {2,4,6} и потребителя реши да въведе число което го няма във масива. Някои дали има някакви идеи ?

от Al.polichronov (1567 точки)


0
Ако К е по голямо или равно на последния елемент от сортирания масив то последния елемент се връща като резултат. Ако К е по малко от първия елемент то в масива не се съдържа число отговарящо на условието. Ако К е равно на първия елемент [0] на сортирания масив то го извеждаме като резултат. С тези проверки трябва да се започне за да се избегнат излишни изчисления, ако никое от тях не е вярно въртим цикъл от К до стойността на втория елемент [1] (на обратно i--) и всяко i го търсим в сортирания масив с binary search-a ---> извеждаме като резултат първото намерено.

от stoyanov (2483 точки)


0
http://pastebin.com/i6UZieXJ

от bsotirov (45 точки)


0
http://pastebin.com/8VesPqBC

от Plamen.Minkov (216 точки)