LeetCode配列コラム:35.挿入位置の検索(C版)

トピックの説明:ソート配列とターゲット値を指定し、配列内でターゲット値を見つけ、インデックスを返します.ターゲット値が配列に存在しない場合は、順番に挿入される位置を返します.配列に重複要素がないと仮定できます.
例1:
入力:[1,3,5,6]、5出力:2
例2:
入力:[1,3,5,6]、2出力:1
例3:
入力:[1,3,5,6]、7出力:4
例4:
入力:[1,3,5,6]、0出力:0
この問題は特に簡単で、たくさんの解法があります.1.二分検索:指定された配列が順序付けされているため、二分検索が優先され、二分検索に失敗すると、最後のhead値がその要素が挿入される位置となります.複雑度解析:時間複雑度:O(logn)空間複雑度:O(1)

int searchInsert(int* nums, int numsSize, int target) {
    int head = 0,rear = numsSize-1;
    int mid = (head+rear)/2;
    while(head<=rear){
        if(target>nums[mid]) head = mid+1;
        else if(targetmid]) rear = mid-1;
        else return mid;
        mid = (head+rear)/2;
    }
    return head;
}

2.スキャン法:配列を前から後ろにスキャンし、nums[i]とtargetの値を比較し、nums[i]>=targetになると、直接returniする.複雑度解析:時間複雑度:O(n)空間複雑度:O(1)

int searchInsert(int* nums, int numsSize, int target) {
    for(int i=0;iif(nums[i]>=target)
            return i;
    }    
    return numsSize;    
}