Java를 사용한 정렬 및 이진 검색



자바 이진트리 구현 (4)

배열을 정렬하고 검색하도록 요청 받았습니다. 배열 정렬은 간단하고 코드는 작동했지만 이진 검색 메서드를 호출 할 때마다 배열의 첫 번째 요소에 대해 작동하지만 "-1"이 결과로 나타납니다

내 전체 코드는 다음과 같습니다.

 public static void main(String[] args) {

    int[] array = new int[5];
    array[0] = 50;
    array[1] = 40;
    array[2] = 10;
    array[3] = 20;
    array[4] = 100;

sort(array, (array.length - 1));

      for (int x = 0; x < array.length; x++) {
        System.out.println(" " + array[x]);
    }
    System.out.println("");
    System.out.println("Binary search (R): " + rBsearch(array, 0, (array.length), 20));
}
    public static void sort(int[] a, int last) {
    if (last > 0) {
        int max = findMax(a, last);
        swap(a, last, max);
        sort(a, last - 1);
    }
}

public static int rBsearch(int[] L, int low, int high, int k) {


    int mid = (low + high) / 2;

    if (low > high) {
        return -1;
    } else if (L[mid] == k) {
        return mid;
    } else if (L[mid] < k) {
        return rBsearch(L, k, mid + 1, high);
    } else {
        return rBsearch(L, k, low, mid - 1);
    }
 }

public static int findMax(int[] arr, int last) {

    int max = 0;
    for (int i = 0; i <= last; i++) {
        if (arr[i] > arr[max]) {
            max = i;
        }
    }
    return max;
    }

public static void swap(int[] arr, int last, int max) {
    int temp = arr[last];
    arr[last] = arr[max];
    arr[max] = temp;
}

  1. 사용자로부터 배열 가져 오기
  2. Java의 Build-In 기능을 사용하여 배열 정렬 ...
  3. 이진 검색을 사용하여 요소 검색 ...

        import java.lang.reflect.Array;
        import java.util.Arrays;
        import java.util.Scanner;
    
        class BinarySearch
        {
           public static void main(String args[])
           {
              int array[];
    
              Scanner input = new Scanner(System.in);
              System.out.println("Enter number of elements:");
             int Size_Of_Array = input.nextInt(); 
    
    
              array = new int[Size_Of_Array];
    
              System.out.println("Enter " + Size_Of_Array + " integers");
    
              for (int counter = 0; counter < Size_Of_Array; counter++)
                  array[counter] = input.nextInt();
    
              Arrays.sort(array);
              System.out.println("Sorting Array is :-");
              for (int counter = 0; counter < Size_Of_Array; counter++)
                  System.out.println(array[counter]);
    
              System.out.println("Enter the search value:");
              int  Searching_item = input.nextInt();
    
              int First_Index=0;
              int Last_Index=Size_Of_Array-1;
              int Middle_Index=(First_Index+Last_Index)/2;
    
              while(First_Index <= Last_Index)
              {
                  if(array[Middle_Index] < Searching_item)
                  {
                      First_Index=Middle_Index+1;
                  }
                  else if ( array[Middle_Index] == Searching_item ) 
                  {
                    System.out.println(Searching_item + " found at location " + (Middle_Index + 1) + ".");
                    break;
                  }
                  else
                  {
                      Last_Index = Middle_Index - 1;
                  }
                  Middle_Index = (First_Index + Last_Index)/2;
    
                  if ( First_Index > Last_Index )
                  {
                      System.out.println(Searching_item + " is not found.\n");
                  }
              }
            }
        }

    BinarySearch 결과


다음 줄에서 rBsearch 메서드를 호출하는 실수를 범했습니다.

else if (L[mid] < k) {
        return rBsearch(L, k, mid + 1, high); 
    } else {
        return rBsearch(L, k, low, mid - 1);
    }

너는 다음을 사용해야한다.

else if (L[mid] < k) {
            return rBsearch(L,  mid + 1, high,k); //the order of the parameters
        } else {
            return rBsearch(L, low, mid - 1,k);
        }

가장 쉬운 방법은 다음과 같습니다. 배열을 목록으로 변환 : Arrays.asList(array)

정렬 용 : Collections#sort

검색 : Collections#binarySearch

이것 좀 봐.


당신은 이진 검색 간격을습니다.

public static int rBsearch(int[] L, int low, int high, int k) {


    int mid = (low + high) / 2;

    if (low > high) {
        return -1;
    } else if (L[mid] == k) {
        return L[mid];
    } else if (L[mid] < k) {
        return rBsearch(L, mid + 1, high, k);
    } else {
        return rBsearch(L, low, mid - 1, k);
    }
 }




recursion