요소를 찾을 수없는 이진 검색의 경우 삽입해야하는 인덱스를 반환하는 방법

Question

이진 검색을 사용하여 요소를 배치 할 배열 인덱스를 찾고 싶습니다. 큰 요소를 아래로 이동하면서 요소를 배열에 삽입하기위한 것입니다. 발견되지 않은 요소를 배치해야하는 위치를 지정하기 위해이 2 진 검색을 어떻게 수정할 수 있습니까?

int binarySearch(int arr[], int x) { 

     int low = 0; 
     int mid = 0; 
     int high = arr.length - 1; 
     while (low <= high) { 
      mid = (low + high)/2; 
      if (x < arr[mid]) { 
       high = mid - 1; 
      } else if (x > arr[mid]) { 
       low = mid + 1; 
      } else { 
       return mid; 
      } 
     } 
     //This is what im trying to get to work 
     if (x < arr[mid]) { 
      return high; 
     } else { 
      return low; 
     } 
    } 

감사합니다.

Answer 1

java.util.Arrays.binarySearch()가 어떻게 수행하는지보십시오.

Answer 2

Arrays.binarySearch()는 -(insertion_point + 1)을 반환합니다. 이렇게하면 반환 값 ≥ 0은 히트이고 <은 0입니다. insertion_point = -return_value - 1입니다.

Answer 3

C++ 표준 템플릿 라이브러리에서 lower_bound 및 upper_bound을 살펴보십시오. 이러한 링크는 사양과 관련이 있습니다. 구현은 동일한 웹 사이트의 구현 섹션에서 stl_algo.h 파일에 있지만 새로운 사용자이므로 한 번에 두 개 이상의 URL을 게시 할 수 없습니다.