LeetCode検索挿入位置35
Gven a sorted array and a target value,return the index if the target is found.If not,return the index where it would be if it were inserted in order.
You may asumeのduplicates in the array.
Example 1:
配列に重複がないと仮定できます.
考え方
二分検索の変形ですね!!
(minとmaxは検索区間であり、検索区間を縮小することでxの値を検索する)
minはヘッドポインタであるmaxは尾のポインターですmid=(min+max)/2
終了条件:min>=max
arr[mid]<x,min=mid+1;
もしarr[mid]>x,max=mid-1;
もしarr[mid]==xなら、結果を見つけます.
見つけられませんでした.どうすればいいですか?
minの値を返したらいいです.最後に見つけたところは一番近いところです.
You may asumeのduplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:Input: [1,3,5,6], 2
Output: 1
Example 3:Input: [1,3,5,6], 7
Output: 4
Example 4:Input: [1,3,5,6], 0
Output: 0
配列と目標値を指定します.ターゲットが見つかったらインデックスを返します.ない場合は、索引の順に挿入された索引を返します.配列に重複がないと仮定できます.
考え方
二分検索の変形ですね!!
(minとmaxは検索区間であり、検索区間を縮小することでxの値を検索する)
minはヘッドポインタであるmaxは尾のポインターですmid=(min+max)/2
終了条件:min>=max
arr[mid]<x,min=mid+1;
もしarr[mid]>x,max=mid-1;
もしarr[mid]==xなら、結果を見つけます.
見つけられませんでした.どうすればいいですか?
minの値を返したらいいです.最後に見つけたところは一番近いところです.
int searchInsert(int* nums, int numsSize, int target) {
int min = 0, max = numsSize - 1, mid;
while(min <= max){
mid = (min + max) / 2;
if(nums[mid] == target) return mid;
if(nums[mid] > target) max = mid - 1;
else min = mid + 1;
}
return min;
}