C# Learning

1. Δυαδική Αναζήτηση

Περιγραφή

Η δυαδική αναζήτηση (Binary Search) είναι ένας αποτελεσματικός αλγόριθμος που χρησιμοποιείται για να βρει ένα στοιχείο σε έναν ταξινομημένο πίνακα. Λειτουργεί με την αρχή της διαίρεσης και κυριαρχίας (divide and conquer), επιτρέποντας τη μείωση του αριθμού των στοιχείων που πρέπει να εξεταστούν σε κάθε βήμα.

Βήματα της Δυαδικής Αναζήτησης

1. Αρχικοποίηση:
   • Ορίζουμε δύο δείκτες: αριστερά (left) και δεξιά (right), που δείχνουν στην αρχή το πρώτο και το τελευταίο στοιχείο του πίνακα, αντίστοιχα.
2. Διαίρεση:
   • Υπολογίζουμε το μέσο (middle) του πίνακα με τη συνθήκη: middle=(αριστεραˊ+δεξιαˊ)/2\text{middle} = \left(\text{αριστερά} + \text{δεξιά}\right) / 2middle=(αριστεραˊ+δεξιαˊ)/2
   • Ελέγχουμε αν το στοιχείο στη θέση middle είναι ίσο με το κλειδί που ψάχνουμε.
3. Κατάκτηση:
   • Αν το στοιχείο στη θέση middle είναι το κλειδί, επιστρέφουμε τη θέση του.
   • Αν το κλειδί είναι μικρότερο από το στοιχείο στη θέση middle, επαναλαμβάνουμε τη διαδικασία για το αριστερό μισό του πίνακα.
   • Αν το κλειδί είναι μεγαλύτερο, επαναλαμβάνουμε τη διαδικασία για το δεξί μισό.
4. Συνέχιση:
   • Συνεχίζουμε τη διαδικασία μέχρι να βρούμε το στοιχείο ή να μην υπάρχουν άλλα στοιχεία να εξετάσουμε (δηλαδή, όταν αριστερά > δεξιά).

Προϋποθέσεις

• Ο πίνακας πρέπει να είναι ταξινομημένος. Αν δεν είναι, η δυαδική αναζήτηση δεν θα λειτουργήσει σωστά.

Χρόνος Εκτέλεσης

Η δυαδική αναζήτηση έχει πολύ καλύτερη απόδοση σε σύγκριση με την απλή γραμμική αναζήτηση. Ο χρόνος εκτέλεσης είναι:

• O(log n), όπου n είναι ο αριθμός των στοιχείων στον πίνακα. Αυτό σημαίνει ότι ο αριθμός των στοιχείων που πρέπει να εξεταστούν μειώνεται στη μέση σε κάθε βήμα.

.

Ψευδογλώσσα

Διαδικασία Δυαδική_Αναζήτηση(πίνακας, αριστερά, δεξιά, κλειδί)
    Αν αριστερά > δεξιά τότε
        Επιστροφή -1
    Τέλος_αν
    
    μέσο <- (αριστερά + δεξιά) / 2
    
    Αν πίνακας[μέσο] = κλειδί τότε
        Επιστροφή μέσο
    Αλλιώς_αν πίνακας[μέσο] > κλειδί τότε
        Επιστροφή Δυαδική_Αναζήτηση(πίνακας, αριστερά, μέσο - 1, κλειδί)
    Αλλιώς
        Επιστροφή Δυαδική_Αναζήτηση(πίνακας, μέσο + 1, δεξιά, κλειδί)
    Τέλος_αν
Τέλος_Διαδικασίας

C#

using System;

class Program
{
    static void Main()
    {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int key = 7;
        int result = BinarySearch(array, 0, array.Length - 1, key);

        if (result != -1)
        {
            Console.WriteLine($"Element {key} found at index: {result}");
        }
        else
        {
            Console.WriteLine($"Element {key} not found in the array.");
        }
    }

    static int BinarySearch(int[] array, int left, int right, int key)
    {
        if (left > right)
            return -1;

        int middle = (left + right) / 2;

        if (array[middle] == key)
            return middle;
        else if (array[middle] > key)
            return BinarySearch(array, left, middle - 1, key);
        else
            return BinarySearch(array, middle + 1, right, key);
    }
}

Ψευδογλώσσα για Αναζήτηση σε Δέντρο

Διαδικασία Αναζήτηση_Δέντρου(κόμβος, τιμή)
    Αν κόμβος είναι null τότε
        Επιστροφή false
    Αν κόμβος.τιμή = τιμή τότε
        Επιστροφή true
    Αλλιώς αν τιμή < κόμβος.τιμή τότε
        Επιστροφή Αναζήτηση_Δέντρου(κόμβος.αριστερό, τιμή)
    Αλλιώς
        Επιστροφή Αναζήτηση_Δέντρου(κόμβος.δεξί, τιμή)
Τέλος_Διαδικασίας

Υλοποίηση σε C#

Ακολουθεί μια υλοποίηση της αναζήτησης σε ένα δυαδικό δέντρο αναζήτησης σε C#.

using System;

class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

class BinarySearchTree
{
    private Node root;

    public BinarySearchTree()
    {
        root = null;
    }

    // Μέθοδος για την εισαγωγή ενός κόμβου
    public void Insert(int value)
    {
        root = InsertRec(root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return root;
        }
        if (value < root.Value)
            root.Left = InsertRec(root.Left, value);
        else if (value > root.Value)
            root.Right = InsertRec(root.Right, value);
        return root;
    }

    // Μέθοδος για αναζήτηση
    public bool Search(int value)
    {
        return SearchRec(root, value);
    }

    private bool SearchRec(Node root, int value)
    {
        if (root == null)
            return false;
        if (root.Value == value)
            return true;
        if (value < root.Value)
            return SearchRec(root.Left, value);
        return SearchRec(root.Right, value);
    }
}

class Program
{
    static void Main()
    {
        BinarySearchTree bst = new BinarySearchTree();

        // Εισαγωγή στοιχείων
        bst.Insert(15);
        bst.Insert(10);
        bst.Insert(20);
        bst.Insert(8);
        bst.Insert(12);
        bst.Insert(17);
        bst.Insert(25);

        // Δοκιμή αναζητήσεων
        Console.WriteLine(bst.Search(10) ? "Element 10 found." : "Element 10 not found.");
        Console.WriteLine(bst.Search(22) ? "Element 22 found." : "Element 22 not found.");
    }
}

Ψευδογλώσσα

Διαδικασία Αναζήτηση_Δέντρου(κόμβος, κλειδί)
    Αν κόμβος είναι NULL τότε
        Επιστροφή NULL
    Τέλος_αν
    
    Αν κόμβος.τιμή = κλειδί τότε
        Επιστροφή κόμβος
    Αλλιώς_αν κλειδί < κόμβος.τιμή τότε
        Επιστροφή Αναζήτηση_Δέντρου(κόμβος.αριστερός, κλειδί)
    Αλλιώς
        Επιστροφή Αναζήτηση_Δέντρου(κόμβος.δεξιός, κλειδί)
    Τέλος_αν
Τέλος_Διαδικασίας

C#

class TreeNode{    public int Value;    public TreeNode Left;    public TreeNode Right;    public TreeNode(int value)    {        Value = value;        Left = null;        Right = null;    }}class Program{    static void Main()    {        TreeNode root = new TreeNode(5);        root.Left = new TreeNode(3);        root.Right = new TreeNode(7);        int key = 3;        TreeNode result = SearchTree(root, key);        if (result != null)        {            Console.WriteLine($"Element {key} found.");        }        else        {            Console.WriteLine($"Element {key} not found.");        }    }    static TreeNode SearchTree(TreeNode node, int key)    {        if (node == null)            return null;        if (node.Value == key)            return node;        else if (key < node.Value)            return SearchTree(node.Left, key);        else            return SearchTree(node.Right, key);    }}

Ψευδογλώσσα

Διαδικασία DFS(κόμβος, επισκέπτες)
    Αν κόμβος είναι NULL ή κόμβος είναι επισκέπτης τότε
        Επιστροφή
    Τέλος_αν

    Πρόσθεση κόμβου στους επισκέπτες
    Για κάθε γείτονα του κόμβου κάνε
        DFS(γείτονας, επισκέπτες)
    Τέλος_Για
Τέλος_Διαδικασίας

C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>
        {
            { 1, new List<int> { 2, 3 } },
            { 2, new List<int> { 4 } },
            { 3, new List<int> { 5 } },
            { 4, new List<int> { } },
            { 5, new List<int> { } }
        };

        HashSet<int> visited = new HashSet<int>();
        DFS(1, graph, visited);
    }

    static void DFS(int node, Dictionary<int, List<int>> graph, HashSet<int> visited)
    {
        if (visited.Contains(node)) return;

        visited.Add(node);
        Console.WriteLine(node);

        foreach (var neighbor in graph[node])
        {
            DFS(neighbor, graph, visited);
        }
    }
}

Η γραμμική αναζήτηση είναι ο απλούστερος τρόπος αναζήτησης. Ελέγχει κάθε στοιχείο της λίστας διαδοχικά μέχρι να βρεθεί το ζητούμενο στοιχείο ή να φτάσουμε στο τέλος της λίστας.

Ψευδογλώσσα

Αλγόριθμος Γραμμική_Αναζήτηση(λίστα, στόχος)  Για κάθε στοιχείο στη λίστα    Αν στοιχείο == στόχος τότε      Επιστροφή Αληθές  Τέλος_αν  Επιστροφή ΨευδέςΤέλος_Αλγορίθμου

C#

bool LinearSearch(int[] list, int target)
{
    foreach (int element in list)
    {
        if (element == target)
        {
            return true;
        }
    }
    return false;
}