C++에서 검색 삽입 위치

<시간/>

정렬된 배열 arr와 대상 값이 있다고 가정하고 대상이 발견되면 인덱스를 찾아야 합니다. 그것이 없으면 순서대로 삽입되었을 때의 인덱스를 반환합니다.

따라서 입력이 [1,3,4,6,6]이고 target =5이면 인덱스 3에 5를 삽입할 수 있으므로 출력은 3이 되므로 배열은 [1,3, 4,5,6,6]

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

n :=A의 크기
n <1이면 -
- 0 반환
낮음 :=0, 높음 :=n - 1
낮음 <=높음, 수행 -
- 중간 :=낮음 + (높음 - 낮음) /2
- A[mid]가 target과 같으면 -
  - 중간 반환
- 그렇지 않으면 A[mid]> target일 때 -
  - 높음 :=중간 - 1, 위치 :=중간
- 그렇지 않으면
  - 낮음 :=중간 + 1, 위치 :=중간 + 1
반환 위치

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int searchInsert(vector<int>& A, int target) {
      int n = A.size();
      if(n < 1) {
         return 0;
      }
      int low = 0;
      int high = n-1;
      int mid;
      int pos;
      while(low <= high) {
         mid = low + (high-low)/2;
         if(A[mid] == target) {
            return mid;
         }
         else if(A[mid] > target) {
            high = mid - 1;
            pos = mid;
         }
         else {
            low = mid + 1;
            pos = mid + 1;
         }
      }
      return pos;
   }
};
main(){
   Solution ob;
   vector<int&g; v = {1,3,4,6,6};
   cout << (ob.searchInsert(v,5));
}

입력

{1,3,4,6,6},5