Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
6.2 kB
6
Indexable
Never
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package bianrysearch;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

/**
 *
 * @author ADMIN
 */
public class BianrySearch {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = InputNumberArray(); // Get the size of the array from user input.
        int[] array = RandomArray(n); // Generate a random array of size 'n'.
        System.out.println("Enter the search value: ");
        int target = sc.nextInt(); // Get the target value from user input.

        SelectionSort(array); // Sort the array using the Selection Sort algorithm.
        PrintArray("Sorted array:", array); // Print the sorted array.

        List<Integer> positions = BinarySearch(array, target); // Perform binary search and store positions.

        if (positions.isEmpty()) {
            System.out.println();
            System.out.println(target + " does not exist");
        } else {
            System.out.println();
            System.out.println("Found " + target + " at Index " + positions);
        }
    }

    public static int InputNumberArray() {
        Scanner scanner = new Scanner(System.in);
        int size;
        while (true) {  // Start an infinite loop to keep asking for input until a valid value is provided.
            try {
                System.out.println("Input Number of Array : ");
                size = Integer.parseInt(scanner.nextLine());  // Read the user's input and parse it as an integer.
                if (size > 0) {
                    break;
                    // if size > 0 , valid value and loop break 
                } else {
                    System.out.println("You have to input a positive number , Reinpiut : ");
                    // iff size <= 0 , Display notice 
                }
            } catch (NumberFormatException e) {
                System.out.println("Invalid value , Reinput : ");
                // if users input a special character , program will notice to users 
            }
        }
        return size;
    }

    public static int[] RandomArray(int ArraySize) {
        // Create an integer array with the specified size 'ArraySize'.
        int[] array = new int[ArraySize];
        // Create a random object name random 
        Random random = new Random();
        for (int i = 0; i < ArraySize; i++) {
            array[i] = random.nextInt(ArraySize);
        } // loop use to random each element of array 
        return array;
    }

    public static void PrintArray(String variable, int[] array) {
        System.out.print(variable);
        System.out.print("[");
        // loop use to accessed each element of array and display them
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(",");
            }
        }// print each element of the array 
        System.out.print("]");
    }

    public static void SelectionSort(int[] arr) {
        int n = arr.length;  // Get the length of the array.

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;  // Assume the first unsorted element is the minimum.

            // Find the minimum element in the unsorted part.
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the minimum element with the first unsorted element.
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static List<Integer> BinarySearch(int[] array, int target) {
        List<Integer> positions = new ArrayList<>(); // Create a list to store positions.
        int left = 0; // Initialize the left pointer to the start of the array.
        int right = array.length - 1; // Initialize the right pointer to the end of the array.

        while (left <= right) { // Continue the loop until the left pointer is less than or equal to the right pointer.
            int middle = left + (right - left) / 2; // Calculate the middle index.

            if (array[middle] == target) { // Check if the middle element is equal to the target.
                positions.add(middle); // If found, add the index to the positions list.
                int LeftIndex = middle - 1; // Initialize a left index for searching on the left side.
                int RightIndex = middle + 1; // Initialize a right index for searching on the right side.

                // Search for additional occurrences of the target on the left side.
                while (LeftIndex >= 0 && array[LeftIndex] == target) {
                    positions.add(LeftIndex); // Add the left index to the positions list.
                    LeftIndex--; // Move the left index to the left.
                }

                // Search for additional occurrences of the target on the right side.
                while (RightIndex <= array.length - 1 && array[RightIndex] == target) {
                    positions.add(RightIndex); // Add the right index to the positions list.
                    RightIndex++; // Move the right index to the right.
                }

                return positions; // Return the list of positions where the target was found.
            } else if (array[middle] < target) { // If the middle element is less than the target,
                left = middle + 1; // Adjust the left pointer to search in the right half.
            } else {
                right = middle - 1; // Otherwise, adjust the right pointer to search in the left half.
            }
        }

        return positions; // Return the list of positions (empty if the target was not found).
    }
}