Wyszukiwanie binarne [C#]

By | 19 listopada 2017

Wyszukiwanie binarne jest algorytmem opierającym się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks. Algorytm, który napisałem korzysta z bibliotek dodatkowych (linq czy Collections.Generic), które są dostępne w C# a niekoniecznie będą dostępne w innych językach programowania, ale jeżeli chodzi o założenia algorytmu to jest on przepisywalny w łatwy sposób na C++ czy JAVA bo semantyka tych języków jest bardzo podobna.

Ważne: Działa on dla listy o wielkości większej niż 1. Nie wdrażałem tego zabezpieczenia z uwagi że generuję losowo listę o ilości elementów większej niż 1.


using System;
using System.Collections.Generic;
using System.Linq;

namespace Wyszukiwanie_binarne
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rand = new Random();

            // tworzę listę i wypełniam losowymi danymi
            List<int> listaLiczb = new List<int>();
            for (int i = 0; i < 100; i++) listaLiczb.Add(rand.Next(0, 1000));

            // czyszczę listę z powtórzonych wartości i sortuję
            listaLiczb = listaLiczb.Distinct().ToList();
            listaLiczb.Sort();

            Console.WriteLine("Liczby na liście:");
            Console.WriteLine(String.Join(",", listaLiczb));

            Console.WriteLine("Podaj liczbę której pozycję szukasz:");
            var szukanaLiczba = int.Parse(Console.ReadLine());

            Console.WriteLine("Poszukiwana liczba znajduje się na liście pod indexem: ");
            try
            {
                Console.Write(Szukaj(listaLiczb, szukanaLiczba));
            }
            catch (Exception)
            {
                Console.Write("Podana liczba nie znajduje się na liście!");
            }

            Console.ReadKey();
        }

        public static int Szukaj(List<int> przeszukiwanaLista, int szukanaLiczba)
        {
            // ilość elementów w liście
            var iloscElementow = przeszukiwanaLista.Count();

            // jeżeli ilość elementów wynosi jeden to znaczy że liczba nie została znaleziona
            if (iloscElementow == 1) throw new Exception("Podana liczba nie znajduje się na liście!");
            
            // wyliczenie połowy z ilości elementów
            var polowa = iloscElementow / 2;

            // wyciągnięcie z listy wartości środkowego elementu
            var srodkowyElement = przeszukiwanaLista[polowa];

            // jeżeli wartość środkowego elementu jest większa niż szukana liczba, to weź pierwszą połowę listy i przekaż do funkcji Szukaj()
            if (srodkowyElement > szukanaLiczba) return Szukaj(przeszukiwanaLista.Take(polowa).ToList(), szukanaLiczba);

            // jeżeli wartość środkowego elementu jest mniejsza niż szukana liczba, to weź drugą połowę listy i przekaż do funkcji Szukaj()
            else if (srodkowyElement < szukanaLiczba) return Szukaj(przeszukiwanaLista.Skip(polowa).ToList(), szukanaLiczba) + polowa; // tutaj dodajemy index połowy, poniważ znaleziona liczba będzie z drugiej połowy listy

            // Jeżeli jest równa co szukana liczba to zwróć index aktualnej połowy
            return polowa;
        }
    }
}


 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *