이진 검색 구현

Question

import java.io.*; 
import java.lang.Integer; 

class sort { 
    public void find(int val, int a[], int n) { 
     int mid = n/2; 
     System.out.println("the mid value is:" + a[mid]); 
     if (a[mid] == val) { 
      System.out.println("found " + a[mid] + " in position " + mid); 
     } else if (a[mid] < val) { 
      for (int i = mid; i < n; i++) { 
       if (a[mid] == val) { 
        System.out.println("found" + val); 
       } 
      } 
     } else if (a[mid] > val) { 
      for (int i =0; i < mid; i++) { 
       if (a[mid] == val) { 
        System.out.println("found" + val); 
       } 
      } 
     } 
    } 


    public static void main(String args[])throws IOException { 
     DataInputStream in = new DataInputStream(System.in); 
     int temp; 
     int a[] = new int[100]; 
     System.out.println("enter the nos of elements"); 
     int n = Integer.parseInt(in.readLine()); 
     for (int i =0; i < n; i++) { 
      a[i] = Integer.parseInt(in.readLine()); 
     } 
     for (int i =0; i < n; i++) { 
      for (int j = i + 1; j < n; j++) { 
       if (a[i] > a[j]) { 
        temp = a[i]; 
        a[i] = a[j]; 
        a[j] = temp; 
       } 
      } 
     } 
     for (int i =0; i < n; i++) { 
      System.out.println(a[i]); 
     } 

     System.out.println("enter the value to be searched"); 
     int val = Integer.parseInt(in.readLine()); 
     sort s = new sort(); 
     s.find(val, a, n); 
    } 
} 

위의 코드에서 이진 검색을 사용하여 기존 배열 목록에서 사용자 정의 값을 찾고 싶습니다. 중간 값만 검사하고 높거나 낮은 값은 검사하지 않습니다.

루프가 제대로 작동하지 않는다고 생각합니다.

이 문제에 대한 해결책을 찾으십시오.

Answer 1

당신이 개 내부 루프 : 당신이 a[mid]에 액세스하는

for(int i=mid;i<n;i++) 
    { 
    if (a[mid] ==val) 
    System.out.println("found"+val); 
} 



    for(int i=0;i<mid;i++) 
{ 
if ( a[mid] ==val) 
    System.out.println("found"+val); 
    } 

알 수 있습니다. mid은 루프 전체에서 변경되지 않습니다. 너 a[i]을 사용했다. mid을 i으로 바꾸어보세요.

또한 코드를 들여 쓰기 할 수 있습니다. 코드를 작성하기 위해 사용하는 편집기는 무엇입니까?

Answer 2

반복적으로 실제로 이진 검색으로 호출 할 수있는 검색에서 값 찾기 위해 아래) 함수를 당신의 발견을 (수정 - 당신의 길이가 제로로 시작 인덱스에서 끝 인덱스와 같은 함수를 호출 할 수 있습니다

public void find(int val, int a[], int startIndex, int endIndex) { 
    if(endIndex-startIndex == 1) { 
     System.out.println("Not found"); 
     return; 
    } 
    int mid = startIndex + ((endIndex-startIndex)/2); 
    System.out.println("the mid value is:" + a[mid]); 
    if (a[mid] == val) { 
     System.out.println("found " + a[mid] + " in position " + mid); 
    } else { 
     if(a[mid] > val) { 
     find(val, a, startIndex, mid); 
     } else { 
     find(val, a, mid, endIndex); 
     } 
    } 
    } 

을 배열 마이너스 1

Answer 3

그 위치로 정의 된 파티션에서 다시 검색을하기 전에 극단적 인 위치 값을 확인하는 것이 좋습니다.