[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

Не знам дали решението ми съвпада с тези на други потребители, но съм използвала wikipedia като източник. Надявам се все пак да съм била полезна на някого :)

http://pastebin.com/LRGTtEnK

 


от vanina_nenova (327 точки)


2
ето нещо и от мен :
http://pastebin.com/NwaM4ZzK
това клипче обяснява нещата доста разбираемо :
http://www.youtube.com/watch?v=wNVCJj642n4

от rosenm (10 точки)


1
Това е моето решение:
http://pastebin.com/YSsqcsWZ
Естествено е използван алгоритъма за двуично обхождане:
http://programming-bg.com/algorithm/7.html
След като се въведат от конзолата елементите на мисава, се въвежда и стойността, която ще търсим в него.
Използвам Array.Sort за сортиране на списъка. В него резделям дължината на списъка и проверявам елемента с този номер, дали отговаря на търсения. Ако -да - прекъсва търсенето и се извежда елемента и номера на конзолата. Ако ли - не - проверявам текущия елемент какъв е по големина спрямо търсения. Ако е по-голям търся по същия начин във втотата част на масива, в противен случай -в първата част. По този начин зациклям до намирането на елемента и номера му в подредения списък.

от nada (0 точки)


0
Моята реализация на двоично търсене итеративно.
Разделянето на всяка стъпка се извършва по средата на текущата част.
Binary search
http://pastebin.com/Z1x6SCUn



1

http://pastebin.com/X2SuhRTZ

Кратко обяснение по решението

- сортираме масива - задължително

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

- вече в едната половина операцията се повтаря докато не намерим търсения елемент или вече не можем да делим


от stanev.plamen (1143 точки)


0
колко хубаво че има активност и от пролетната група :)

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


1

1 while 3 if + bonus "not a member" http://pastebin.com/aEmwx47m

                 arr[ decrInd---------?-------mid index ---?------incrInd>>> ]
midIndex = (decreaceInd + increaceInd) / 2;
if -че arr[----?--------mid index----->]
search in <<<<<-------this direction
                  arr[decrId(same) ------?---mid Index----incrInd(midIndex-1)>>]
if -че  arr[--------mid index---?----->]
search in ----->>>>> this direction
                    arr[ decrId(midIndex+1) ------?---mid Index----incrInd(same)>>]

-1/+1 започва от следващия елемент може и без него но така се ползва бонуса на алгоритъма, -/+ оказва посоката имайки предвид че arr е възходящо сортиран


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


0
Здравей, Алготиръма ти е интересен и на мен ми хареса, Можеш да сложиш само едно break; (или по скоро Environment.Exit(0) ) так където изписваш че не може да се намери елемента (ако търси несъществуваща стойност), защото иначе влиза в безкраен цикъл.

от stanev.plamen (1143 точки)


0
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 
            int numder = 4;
 
            int end = array.Length;
 
            int start = 0;
 
            int mid = (end + start) / 2;
 
            while (start<=mid)
            {
                start++;
                if (array[start]==numder)
                {
                    Console.WriteLine("Index {0} value {1}",start,numder);
                    return;
                }
            }
 
            while (end<mid)
            {
                end--;
                if (array[end]==numder)
                {
                    Console.WriteLine("Index {0} value {1}",end, numder);
                    return;
                }
            }
Ето го и моето решение.

от Petar Atanasov (0 точки)


0

Ето едно интересно решение и от мен: http://pastebin.com/8A8Zq7j1

Програмата първо сортира масива, след това намира средният елемент от масива и проверява дали числото което търсим е по-голямо или по-малко от средния елемент.

Ако е по-голямо - проверява в дясно от средата и намира средния елемент от дясната половина (тоест дясната четвърт след средата)

Ако е по-малко - проверява в ляво от средата и намира средния елемент от лявата половина (тоест лявата четвърт преди средата)

Сравняваме търсеното число със средният елемент на всяка нова редица и освен това за спестяване на работа проверява средният елемент + - 1 елемент преди-след средата. Така по-бързо намираме каквото търсим :)

И така проверката продължава докато не намерим правилното число.




1

Добавих няколко екстри за по-добър "user experience" хахах и се получи това: http://git.io/v2qAUQ . Естествено, на цената на десетки редове код :Р

Допълнителното е, че търси и принтира всички елементи равни на търсения елемент... със запетайки и точки и т.н, хах.

Сигурно има и по-отпимални начини за изпълнението на този алгоритъм, но това измислих и ми отне повече време, отколкото очаквах, та вече готови имплементации ще разгледам утре, май си струва да ги погледна.


от georgiwe (720 точки)


0
Браво!! Наистина е добро! Най-много ми харесва това, че връща резултат, дори когато търсеното число не съществува в масива - (докато индекса е различен от големия и едновременно различен от малкия) - условието на външния while.

от Evgenia Hristova (0 точки)

0
Благодаря :) Тъкмо се чудех дали има смисъл да поствам и останалите решения. Радвам се, че някой чете
Условието за край ми хрумна по едно време и после докато дойде време да го напиша, го забравих. И след тва, не знам защо, го мислих немалко време докато пак се сетя какво беше :))
Поздрави

от georgiwe (720 точки)


0

GitHub

Определям mid по този начин за да не се получи препълване (2 000 000 000 + 1000000000 = 3000000000 което си препълва инта преди да се раздели на 2)


от dzhenko (3893 точки)