[자바] InsertInOrder에서 재귀 이진 검색 사용

질문 ???에 최신 코드를 복사 했습니까? 한 가지 분명한 문제는 다음과 같습니다.

int belongs = -( bSearch( arr, 0, arr.length-1, newVal)) - 1;

 

bSearch

메서드 는 배열에서 값을 찾을 수없는 경우 -1을 반환합니다. newValue를 찾을 수 없을 때 삽입 지점 -2를 제공합니다. 항목을 찾았

는지

여부와 위치를 모두 반환 하려면 bSearch 를 변경해야합니다 . 두 가지 옵션

1. 새 클래스 생성 (및 반환)

   private class FoundResult {
           boolean found = true;
               int position;
               }
               

2. 찾을 수없는 경우 return -hi-1 ie in bSearch 다음과 같이

   if(lo>hi)
          return -hi-1;
          

---

옵션 1의 경우 코드는 대략 다음과 같습니다 (테스트하지 않았습니다).

static void insertInOrder( int[] arr, int cnt, int newVal )     {

    int belongs = bSearch( arr, 0, arr.length-1, newVal)).position ;
        for ( int i = cnt; i >= belongs+1 ; --i) {
               arr[i] = arr[i-1];
                   }
                   
                       arr[belongs] = newVal;
                       }
                       
                       // We do not need to pass in count. The incoming lo and hi define the range
                       public static FoundResult bSearch(int[] a, int lo, int hi, int key)
                       {
                       int mid = (lo+hi)/2;
                       FoundResult ret;
                       if(lo>hi) {
                           ret = new FoundResult();
                               ret.found = false;
                                   ret.position = hi;
                                       return ret;
                                       } else if (a[mid]==key) {
                                           ret = new FoundResult();
                                               ret.position = hi;
                                                   return ret;
                                                   } else if (a[mid]<key) {
                                                       return bSearch(a, mid+1, hi, key);
                                                       } else {
                                                           return bSearch(a, lo, mid-1, key);
                                                           }
                                                           

---

옵션 2의 경우 코드는 대략 다음과 같습니다.

static void insertInOrder( int[] arr, int cnt, int newVal )     {

    int belongs = bSearch( arr, 0, arr.length-1, newVal)) ;
        if (belongs < 0) {
                belongs  = -1 - belongs ;
                    }
                        for ( int i = cnt; i >= belongs+1 ; --i) {
                               arr[i] = arr[i-1];
                                   }
                                   
                                       arr[belongs] = newVal;
                                       }
                                       
                                       // We do not need to pass in count. The incoming lo and hi define the range
                                       public static int bSearch(int[] a, int lo, int hi, int key)
                                       {
                                       int mid = (lo+hi)/2;
                                       FoundResult ret;
                                       if(lo>hi) {
                                           return - hi - 1;
                                           } else if (a[mid]==key) {
                                               return hi;
                                               } else if (a[mid]<key) {
                                                   return bSearch(a, mid+1, hi, key);
                                                   } else {
                                                       return bSearch(a, lo, mid-1, key);
                                                       }
                                                       

출처
https://stackoverflow.com/questions/22079792