자료구조와 함께 배우는 알고리즘 입문[자바] - 5일차

03. 검색

 

연습문제 Q3

static int searchIdx(int[] a, int n, int key, int[] idx) {
     int count = 0;
     for(int i=0; i<n; i++) {
         if(a[i] == key) {
              idx[count++] = i;
         }
     }
     return count;
}

 

public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);

      System.out.print("배열 크기 ::: ");

      int num = sc.nextInt();
      int[] x = new int[num+1];
      int[] idx = new int[num];

      for(int i=0; i<num; i++) {

           System.out.print("x["+i+"]" ::: ");

           x[i] = sc.nextInt();
      }

      System.out.print("검색할 값 ::: ");

      int key = sc.nextInt();

 

      int cnt = searchIdx(x, num, key, idx);
      if(cnt == 0) {
           System.out.println("그 값의 요소가 없습니다.");
      }else{
           System.out.println(cnt);
      }

}

 

 

연습문제 Q4

static int binSearch(int[] a, int key) {
     int idx = 0;
     int first = 0;
     int end = a.length-1;

 

     System.out.print("  |");

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

          System.out.printf("%2d", i);

     }

 

     System.out.print("\n--+");

     for(int i=0; i<a.length; i++) {
           if(i == a.length-1) {

                System.out.print("--\n");

           }else{

                System.out.print("--");

           }

     }

 

     while(first<=end) {

          System.out.print("  |");

          idx = (first+end)/2;

 

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

                if(i == idx) {

                     System.out.printf("%2s","+");

                }else if(i == first) {

                     System.out.printf("%2s","<-");

                }else if(i == end){

                     System.out.printf("%2s","->");

                }else{

                     System.out.printf("%2s","");

                }

          }

 

          System.out.print("\n"+idx+" |");

          for(int j=0; j<a.length; j++) {

              System.out.print("%2d", a[j]);

          }

          System.out.println();

 

          if(a[idx] == key) {
                return idx;
          }else if(a[idx] > key) {

                end = idx -1;
          }else{
                first = idx + 1;
          }

          System.out.println("\n  |");
     } 
     return -1;
}

 

public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);

      System.out.print("배열 크기 ::: ");

      int num = sc.nextInt();
      int[] x = new int[num+1];
      int[] idx = new int[num];

      for(int i=0; i<num; i++) {

           System.out.print("x["+i+"]" ::: ");

           x[i] = sc.nextInt();
      }

      System.out.print("검색할 값 ::: ");

      int key = sc.nextInt();

 

    int idx = binSearch(x, key);

    if(idx == -1) {
          System.out.println("그 값의 요소가 없습니다.");
    }else{
          System.out.println(key+"는 x["+idx+"]에 있습니다.");
    }

}

 

 

연습문제 Q5

static int binSearchX(int[] a, int n, int key) {
     int idx = 0;
     int first = 0;
     int end = n-1;

     while(first<=end) {
          idx = (first+end)/2;
          if(a[idx] == key) {
               int pc = idx;
               while(a[pc] == key) {
                    pc--;
               }
               return pc+1;
          }else if(a[idx] > key) {
               end = idx -1;
          }else{
               first = idx + 1;
          }
     }     
     return -1;
}

 

public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);

      System.out.print("배열 크기 ::: ");

      int num = sc.nextInt();
      int[] x = new int[num+1];
      int[] idx = new int[num];

      for(int i=0; i<num; i++) {

           System.out.print("x["+i+"]" ::: ");

           x[i] = sc.nextInt();
      }

      System.out.print("검색할 값 ::: ");

      int key = sc.nextInt();

 

    int idx = binSearchX(x, num, key);

    if(idx == -1) {
          System.out.println("그 값의 요소가 없습니다.");
    }else{
          System.out.println(key+"는 x["+idx+"]에 있습니다.");
    }

}

 

 

연습문제 Q6

public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);

     System.out.print("요솟수 ::: ");

     int num = sc.nextInt();
     int[] x= new int[num];

     System.out.println("오름차순으로 입력하세요.");

     System.out.print("x[0] ::: ");

     for(int i=1; i<num; i++) {
          do {

              System.out.print("x["+i+"] :: ");

              x[i] = sc.nextInt();
          }while(x[i] <= x[i-1]);
     }

     System.out.print("검색할 값 ::: ");

     int key = sc.nextInt();

     int idx = Arrays.binarySearch(x, key);

     if(idx < 0) {

          System.out.print("그 값의 요소가 없습니다. 삽입포인트 ::: "+(-num-1));

     }else{

          System.out.println(key+"은(는) x["+idx+"]에 있습니다.");
     }
}

 

연습문제 Q7

static class PhyscData {
    private String name;
    private int height;
    private double vision;
        
    public PhyscData(String name, int height, double vision) {
        this.name = name;
        this.height = height;
        this.vision = vision;
    }
    
    public String toString() {
        return name+", "+height+", "+vision;
    }
        
    public static final Comparator<PhyscData> VISION_ORDER = new VisionOrderComparator();
    
    private static class VisionOrderComparator implements Comparator<PhyscData> {
        @Override
        public int compare(PhyscData o1, PhyscData o2) {
            return (o1.vision > o2.vision) ? 1 : (o1.vision < o2.vision) ? -1 : 0;
        }
    }
}
 
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
        
    PhyscData[] x = {
        new PhyscData("테스트1", 162, 0.3),
        new PhyscData("테스트2", 152, 1.3),
        new PhyscData("테스트3", 180, 1.9),
        new PhyscData("테스트4", 152, 2.0),
        new PhyscData("테스트5", 175, 1.5),
        new PhyscData("테스트6", 190, 1.8),
        new PhyscData("테스트7", 174, 0.2)
    };
        
    System.out.print("시력이 몇인 사람을 찾고 있나요? : ");
        
    double vision = sc.nextDouble();
    int idx = Arrays.binarySearch(x, new PhyscData("", 0, vision), PhyscData.VISION_ORDER);
        
    if(idx < 0) {
        System.out.println("요소가 없습니다.");
    }else{
        System.out.println("x["+idx+"]에 있습니다.");
        System.out.println("찾은 데이터 ::: "+x[idx]);
    }        
}