Leetcode search insert location

Power button 35. Search insert location

 

  The title requires you to find a number , And if the target element doesn't return where it should be inserted in the array , The title prompt array is an ascending array without repeating elements , obviously , This just meets the requirements of binary search , It's easy to find elements by setting a binary template , But what about inserting ？,

for instance

For example, we are going to be in 1 3 5 6 Find number 2, And insert position , We can use binary search

We can find that the intermediate element is 3, But keep looking 2,

 

  We don't have 2, but 2 The position to be inserted is 3 The location of , That is to say, we will 2 Insert into 3 And the subscript is 1 Location , However, if you perform the previous step, you will never find the location to insert , So we just need to find the first element that is greater than or equal to the target element , If the intermediate element is exactly equal to the target element , Then return the target element subscript , If it is larger than the target element , This position is where the target element is to be inserted , But there's one more thing , If it is not found in the array and there is no position in the array to insert , It must be larger than all the elements in the array , Then insert it after the last element , That is, the subscript is the array size , So we can define a ans Is the size of the array , If not found in the array , We just insert it to the next position of the last element in the array .

int searchInsert(int* nums, int numsSize, int target){
      int left =0;
      int right = numsSize-1;
      int ans =numsSize;//(1)
      while(left<=right){//（2）
          int mid =(right-left)/2+left;
          if(nums[mid]>=target){//(3)
            ans =mid;
            right =mid-1;
          }
          else{
              left=mid+1;
          }
      }
       return ans;//(4)
}

1）： To find if the target element is not in the array and is larger than the element in the array , It must be inserted where the subscript is the size of the array

2）： Adopt left closing and right closing

3）： If the intermediate element is exactly equal to the target element , Then return the target element subscript , If it is larger than the target element , This position is where the target element is to be inserted

4): If it is not found in the array and there is no position in the array to insert , It must be larger than all the elements in the array , Then insert it after the last element , That is, the subscript is the array size