[leetcode 35][c++] search Insert Position

문제 : 

 

 

알고있어야 할 점. 

"return low" 한다. 그 이유는. 

배열에 [1,5] 가 들어있을경우, 

high = low +1 이고, mid = low 이다.

이걸 아래와 같이 나눠서 생각하면 

각 변수의 인덱스는 l = 0, h = 1, m = 0 이다. 

case 1) target = 0 이면,
          target < nums[mid]이고, 따라서 high = mid-1이고, h=-1 이된다. 
          [1,   5]

      ↑  ↑   

      h    l
        

case 2) target = 4 이면
          target > nums[mid] 면, low=mid+1 이므로, 1회 진행시 h,l,m이 같은 값을 가르킨다. 
          [1,   5]

              ↑↑↑ 

               h l m

         다시 target이 5보다 작으므로, h=mid-1이고

        [1,   5]

        ↑   ↑

        h     l  이 된다. 

case 3) target = 6 이면

        target > nums[mid] 면, low=mid+1 이므로, 1회 진행시 h,l,m이 같은 값을 가르킨다. 
          [1,   5]

              ↑↑↑ 

               h l m

        이때, case2와 다르게, target 이 5보다 크므로, l=mid+1이다. 

 

 

1,2,3 case확인시 low를 반환해야 삽입하려는 위치가 나옴을 알 수 있다. 

따라서 데이터를 찾지 못했다면, low를 반환한다. 

 

 

출처 :  leetcode priyarm_vd 님

https://leetcode.com/problems/search-insert-position/discuss/1596479/C%2B%2B-or-3-Solutions-or-Well-explained-with-example-and-concise-solution

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
     
        int low = 0, high = nums.size()-1;
        
        while(low<=high){
            int mid = low + (high-low)/2;
            
            if(nums[mid] == target) return mid;
            
            else if(nums[mid] > target) high = mid-1;
            
            else low = mid+1;
        }
        return low;
    }
};