바이너리 검색이 실패한 경우 찾기

Question

정말 흥미로운 프로그래밍 문제를 해결하기 위해 노력하고 있으며 필자는 코드가 실패한 이유를 설명하지 않습니다. 여기있다 :

쓰기리스트와 목표 합 주어진 합 대상 합 임의의 두 가지 요소 제로 인덱스를 반환하는 함수. 이러한 요소가 없으면 함수는 을 반환해야합니다. 예를 들어 는 findTwoSum는 (새로운 INT은 [{1, 3, 5, 7, 9}, 12)의 인덱스는 다음 튜플 하나를 반환해야

1, 4 (3 + 9 = 12) 
2, 3 (5 + 7 = 12) 
3, 2 (7 + 5 = 12) 
4, 1 (9 + 3 = 12) 

간단한 오른쪽되어야 하는가? 그래서 여기 내 함수는 다음과 같습니다

public static int[] findTwoSum(int[] list, int sum) { 
     int[] indices = null; 
     for(int i = 0; i < list.length; i++) { 
      int currentNum = list[i]; 
      int findNum = sum - currentNum; 
      int length = list.length; 
      int min = i; 
      int max = length-1; 

      while(max >= min) { 
       int guess = (max+min)/2; 

       if(list[guess] == findNum) { 
        return new int[] {i,guess}; 
       } 

       if(list[guess] < findNum) { 
        min = guess + 1; 
       } 

       if(list[guess] > findNum) { 
        max = guess - 1; 
       } 
      } 

     } 


     return indices; 
    } 

코드는 매우 간단하다 배열의 모든 요소에 대해, 그들의 합이 제공 sum 같도록, 이진 검색, 다른 요소를 사용하여 찾습니다. 이 코드를 테스트했는데 제공된 배열이 정렬되었다고 가정하면 실패하는 시나리오를 찾을 수 없습니다. 그러나,이 코드를 TestDome에서 실행할 때, 마지막 케이스가 실패합니다. 어떻게 든 잘못된 해결책입니다. 아무도이 접근 방식에있어 잘못된 점을 지적 할 수 있습니까?

Answer 1

코드는 목록이 정렬되어 있다고 가정합니다. 문제 문은 요소의 순서에 대해서는 아무 것도 말하지 않으므로 배열을 직접 정렬해야합니다. 인덱스가 필요하므로 값과 인덱스의 쌍을 정렬해야합니다.

더 빠른 방법은 데이터를 개수 및 원래 인덱스가있는 해시 맵에 저장하고 목록에있는 각 n에 대해 Target - n의 존재를 확인하는 것입니다. Target이 2*n 일 때 특별한 경우에 대한 계산이 필요합니다.

Answer 2

초기 목록의 정렬 된 순서와 관련하여 작성자의 질문과 설명을 바탕으로 초기 목록이 정렬되지 않은 것처럼 보입니다. 따라서 목록을 정렬해야하고 원래 색인을 다른 목록에 별도로 저장해야합니다.

배열을 정렬하고 원래 색인을 기록한 후 arr[]에는 정렬 된 목록이 포함되고 indices[]에는 해당 요소의 원래 색인이 arr[]에 포함되어 있다고 가정 해 보겠습니다. 간단한 단어로 indices[i]은 요소의 원래 색인 arr[i]을 제공합니다.

이제 쌍을 찾기 위해 2 SUM 알고리즘을 따를 수 :

• 초기화 두 개의 인덱스 변수를 후보에게 정렬 된 배열에 요소를 찾을 수 있습니다.

  • 초기화 제 좌단 인덱스 : l = 0
  • 초기화 제 우단 인덱스 : R = 1 ar_size

• 루프 L < R있다.

  • 경우 리턴 쌍 (지수 [L], 인덱스 (R)) ([L] + 도착 [R] == 합 도착) 그렇지
  • 경우 (도착 [L] + 도착 [R] NULL

  또한 대신 2-SUM 절차의 이진 검색 기술을 사용할 수 있습니다 반환하지 - 전체 배열의 어떤 후보자 다른 r-- 사용

< 합) 다음 리터 ++.

희망이 있습니다!

Answer 3

이 솔루션을 사용해보십시오. 배열을 정렬하고 이진 탐색을 사용하여 sum-n이어야하는 두 번째 요소를 찾습니다.

일치하는 쌍을 찾을 경우, 원래 인덱스를 결정하기 위해 원래의 배열에 조회됩니다 :

public static int[] findTwoSum(int[] list, int sum) { 
    int len = list.length; 
    int[] sortedList= Arrays.copyOf(list, len); 
    Arrays.sort(sortedList); 
    for (int i = 0; i < len; i++) { 
     int m = list[i]; 
     int j = Arrays.binarySearch(sortedList, sum - m); 
     if (j >= 0 && i != j) 
      return new int[] { i, findIndex(list, sortedList[j]) }; 
    } 
    return null; 
} 

public static int findIndex(int[] list, int m) { 
    int len = list.length; 
    for (int i = 0; i < len; i++) { 
     if (list[i] == m) 
      return i; 
    } 
    return -1; 
}