Arama algoritmalarının her birini detaylı anlat, Java ile kodla

Arama algoritmaları, bir veri kümesi içinde belirli bir değeri veya koşulu karşılayan öğeleri bulmak için kullanılır. En yaygın arama algoritmaları; Doğrusal (Lineer) Arama, İkili (Binary) Arama, Derinlik İlk Arama (Depth-First Search, DFS) ve Genişlik İlk Arama (Breadth-First Search, BFS)'dır. Her birinin Java dilinde nasıl kodlanabileceğine dair detaylı açıklamalar ve örnekler aşağıda verilmiştir.

1. Doğrusal Arama (Linear Search)

Doğrusal arama, bir dizideki her öğeyi sırayla kontrol ederek aranan değeri bulur. Eğer aranan değer bulunursa, değerin konumu döndürülür. Aksi takdirde, arama başarısız olur.

java

Copy code

public class LinearSearch {

    public static int linearSearch(int[] arr, int key) {

        for (int i = 0; i < arr.length; i++) {

            if (arr[i] == key) {

                return i;

            }

        }

        return -1;

    }

    public static void main(String[] args) {

        int[] arr = {10, 20, 30, 40, 50};

        int key = 30;

        int result = linearSearch(arr, key);

        if (result == -1) {

            System.out.println("Element is not found in the array");

        } else {

            System.out.println("Element is found at index: " + result);

        }

    }

}

2. İkili Arama (Binary Search)

İkili arama, sıralı bir dizide arama yaparak aranan değeri daha hızlı bulur. Her adımda, dizinin ortasındaki değer aranan değerle karşılaştırılır. Eğer aranan değer ortadaki değerden küçükse, arama sol yarıda devam eder. Büyükse, sağ yarıda devam eder.

java

Copy code

public class BinarySearch {

    public static int binarySearch(int[] arr, int key) {

        int low = 0;

        int high = arr.length - 1;

        

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (arr[mid] == key) {

                return mid;

            } else if (arr[mid] < key) {

                low = mid + 1;

            } else {

                high = mid - 1;

            }

        }

        return -1;

    }

    public static void main(String[] args) {

        int[] arr = {10, 20, 30, 40, 50};

        int key = 30;

        int result = binarySearch(arr, key);

        if (result == -1) {

            System.out.println("Element not found");

        } else {

            System.out.println("Element found at index: " + result);

        }

    }

}

3. Derinlik İlk Arama (DFS)

DFS, bir graf veya ağaç yapısında, derinliğe doğru ilerleyerek arama yapar. Bir düğümden başlayarak, o düğümün çocuklarına gidilir ve bu süreç, daha fazla çocuk kalmayıncaya kadar devam eder. Ardından, geri dönülerek diğer çocuklar üzerinden ilerlenir.

DFS için bir ağaç yapısında örnek:

java

Copy code

class Node {

    int value;

    Node left, right;

    

    public Node(int item) {

        value = item;

        left = right = null;

    }

}

public class DFS {

    Node root;

    

    void DFSUtil(Node node) {

        if (node == null) {

            return;

        }

        // Öncelikle sol çocuğu ziyaret et

        DFSUtil(node.left);

        

        // Düğümü ziyaret et

        System.out.print(node.value + " ");

        

        // Sonra sağ çocuğu ziyaret et

        DFSUtil(node.right);

    }

    void DFS() {

        DFSUtil(root);

    }

    public static void main(String[] args) {

        DFS tree = new DFS();

        

        // Ağacın düğümlerini oluştur

        tree.root = new

User

devam et

ChatGPT

Node(1);

tree.root.left = new Node(2);

tree.root.right = new Node(3);

tree.root.left.left = new Node(4);

tree.root.left.right = new Node(5);

csharp

Copy code

    System.out.println("DFS traversal of binary tree is ");

    tree.DFS();

}

}

scss

Copy code

Bu kod örneği, bir ikili ağaç yapısında derinlik ilk arama (DFS) algoritmasının nasıl uygulanabileceğini göstermektedir. `DFS()` metodu, kökten başlayarak ağacı derinlik ilk pre-order tarzında gezinir.

### 4. Genişlik İlk Arama (BFS)

Genişlik İlk Arama (Breadth-First Search - BFS) algoritması, bir graf veya ağaç yapısındaki düğümleri en yakından en uzağa doğru katman katman ziyaret eder. Bu algoritma, özellikle en kısa yol problemleri veya bir düğümden diğerine olan en kısa mesafeyi hesaplama gibi durumlar için kullanılır. BFS, bir kuyruk yapısını kullanarak her seviyedeki tüm düğümleri ziyaret eder ve ardından bir sonraki seviyeye geçer.

Java'da BFS algoritmasını uygulamak için öncelikle bir ağaç veya graf yapısına ihtiyacımız var. Bu örnekte, basit bir ikili ağaç üzerinde BFS uygulayacağız. Ağaç düğümleri için bir Node sınıfı tanımlayacağız ve BFS işlemini gerçekleştiren bir metot yazacağız.

java

Copy code

import java.util.LinkedList;

import java.util.Queue;

// Ağaç düğümünü temsil eden sınıf

class Node {

    int value;

    Node left, right;

    public Node(int value) {

        this.value = value;

        left = null;

        right = null;

    }

}

public class BinaryTreeBFS {

    Node root;

    // BFS algoritmasını uygulayan metot

    public void breadthFirstSearch() {

        Queue<Node> queue = new LinkedList<>();

        

        // Kök düğüm kuyruğa eklenir

        queue.add(root);

        while (!queue.isEmpty()) {

            // Kuyruktan bir düğüm çıkarılır ve işlenir

            Node current = queue.poll();

            System.out.print(current.value + " ");

            // Çıkarılan düğümün sol çocuğu varsa kuyruğa eklenir

            if (current.left != null) {

                queue.add(current.left);

            }

            // Çıkarılan düğümün sağ çocuğu varsa kuyruğa eklenir

            if (current.right != null) {

                queue.add(current.right);

            }

        }

    }

    public static void main(String[] args) {

        BinaryTreeBFS tree = new BinaryTreeBFS();

        // Ağaç yapısını oluşturuyoruz

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        System.out.println("Binary Tree Breadth First Search:");

        tree.breadthFirstSearch();

    }

}

Bu kod parçası, bir ikili ağaçta BFS algoritmasını nasıl uygulayabileceğinizi gösterir. breadthFirstSearch metodu, ağacı katman katman ziyaret eder ve düğümlerin değerlerini ekrana basar. Bu işlem, bir Queue (Kuyruk) yapısını kullanarak gerçekleştirilir. Kuyruk, ilk girenin ilk çıktığı (FIFO - First In First Out) bir veri yapısıdır ve BFS'nin temelini oluşturur. Her iterasyonda, kuyruktan bir düğüm çıkarılır, işlenir ve ardından bu düğümün tüm çocukları kuyruğa eklenir. Bu süreç, kuyruk boşalana kadar devam eder.