主題
難度: Easy
===========================================================================
說明:
給予已按遞增排序的陣列資料與目標值,若找到目標值則返回index,
若沒有則返回按順序所插入的index,
必須使用時間複雜度為O(log n)的演算法.
===========================================================================
測資1:
Input: nums = [1,3,5,6], target = 5
Output: 2
測資2:
Input: nums = [1,3,5,6], target = 7
Output: 4
測資3:
Input: nums = [1], target = 0
Output: 0
===========================================================================
條件限制:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums為遞增排序
-10^4 <= target <= 10^4
===========================================================================
解題:
最值觀的就是遍歷陣列進行排序,但有限制時間複雜度為O(log n),故使用Binary Search,
建立左,右,中三個指標
左邊指標由0開始,右邊指標由nums的最後一個index開始,
1.中間指標則由左邊+右邊指標位置除2而得,
2.如果中間指標=目標值,表示已找到目標值,則返回中間指標的位置
3.若中間指標>目標值,則右方指標位置=中間指標位置
4.否則左方指標位置=中間指標位置
5.重複1~4左右指標的位置移位,直到左右指標的位置在隔壁則停止搜索
public class Solution
{
public int SearchInsert(int[] nums, int target)
{
int left = 0; //左邊指標
int right = nums.Length - 1; //右邊指標
int mid = 0; //中間值
while(left+1<right)
{
mid = left + (right - left) / 2; //取左與右指標的中間值開始搜索
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
right = mid;
else
left = mid;
}
if (nums[right] < target) //如果所有值皆比target小 ex:nums = [1,3,5,6], target = 7
return nums.Length;
else if (nums[left] >= target)
return left;
else
return right;
}
}
達人
