35. Search Insert Position
【题目】
Given 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 assume no 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
【思路】
這邊用BinarySearch 二分搜尋去找會比較適合，蠻簡單的。
【解法】
☆JAVA
等同下方解法
public static int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while( left <= right){
int min = (left + right)/2;
if(nums[min]>target){
right = min - 1;
}else if (nums[min]<target){
left = min + 1;
}else{
return target;
}
}
return left;
}
☆Python
簡述一下解法
假設陣列長度是10，有10個元素在陣列內，目標值是找到3的位置
[1,3,4,5,6,7,8,9,11,12]
那一開始 設置 左邊指標=0 右邊指標= (10-1) = 9 (因為指標從0開始)
(一)
- |-0-|--|--|--|--|-5-|--|--|--|-9-|
- 這樣我們就用二分法先取中間去比較
- 所以計算平均值 =(左邊指標+右邊指標/2) = (0+9)/2 = 4.5 = 取四捨五入 = 5
- 陣列[5] = 7
- 7因為比3 目標值大 ，所以我們縮短範圍
- 我們把右邊指標二分法掉 ，所以 右邊指標 = 5(平均值) - 1 (指標要隨者左右位移)= 4
(二)
- 所以目前指標位置如下
- |-0-|--|--|--|-4-|
- 所以計算平均值 = (左邊指標+右邊指標/2) = (0+4)/2 = = 2
- 陣列[2] = 4
- 4因為比3 目標值大 ，所以我們縮短範圍
- 我們再把右邊指標二分法掉 ，所以 右邊指標 = 2(平均值) - 1 (指標要隨者左右位移)= 1
(三)
- 所以目前指標位置如下
- |-0-|-1-|
- 所以計算平均值 = (左邊指標+右邊指標/2) = (0+1)/2 = = 0.5 = 取四捨五入 = 1
- 陣列[1] = 3
- 找到 3 了 ，所以回傳 平均值 1
(三+Plus)
- 我們再假設目標值改成找 2 好了
- |-0-|-1-|
- 所以計算平均值 = (左邊指標+右邊指標/2) = (0+1)/2 = = 0.5 = 取四捨五入 = 1
- 陣列[1] = 3
- 3因為比2 目標值大 ，所以我們縮短範圍
- 我們再把右邊指標二分法掉 ，所以 右邊指標 = 1(平均值) - 1 (指標要隨者左右位移)= 0
- 根據條件 因為 0<=0 表示說這是臨界點了
- 那我們直接回傳最小Left 代表這是他應該的位置 Cool !!
- [1,2,3,4,5,6,7,8,9,11,12]
class Solution:
def searchInsert(self, A, target):
left = 0; right = len(A) - 1
while left <= right:
mid = ( left + right ) // 2
if A[mid] < target:
left = mid + 1
elif A[mid] > target:
right = mid - 1
else:
return mid
return left