DAY 7
4
Software Development

## [Day 7] 從LeetCode學演算法 - 0035. Search Insert Position (Easy)

``````Question:
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
``````

mid左邊的數必然小於mid，反之mid右邊的數必然大於mid
(按順序排的嘛XD)

nums[1]為3, 3 > 2 -> 將up改為mi-1=0 -> mi = (0 + 0) / 2 = 0 ->
nums[0]為1, 1 < 2 -> 將lo改為mi+1=1 ->
lo和up已交叉，故結果應輸出1。

``````lo  up  mi  nums[mi]
0   3   1   3
0   0   0   1
1   0   0   1
``````

nums[1]為3, 3 < 5 -> 將lo改為mi+1=2 ->mi = (2+3)/2 = 2 ->
nums[2]為5, 5==5 -> 直接輸出mi的值2即是答案。

``````lo  up  mi  nums[mi]
0   3   1   3
2   3   2   5
``````

nums=[1,3,5,6], target=7 -> ans = 4

``````lo  up  mi  nums[mi]
0   3   1   3
2   3   2   5
3   3   3   6
4   3   3   6
``````

nums=[1,3,5,6], target=0 -> ans = 0

``````lo  up  mi  nums[mi]
0   3   1   3
0   0   0   1
0   -1  -1  6        #(這個是用python輸出的，所以nums[-1] == 6)
``````

Java:

``````class Solution {
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int i = 0, j = nums.length-1;
int index = -1;
while(i <= j) {
index = (i + j) / 2;
if(nums[index] == target)
return index;
if(nums[index] >= target)
j = index - 1;
else
i = index + 1;
}
return i;
}
}
``````

Python:

``````class Solution:
def searchInsert(self, nums: 'List[int]', target: 'int') -> 'int':
lo, up = 0, len(nums) - 1
mi = (lo + up) // 2
while lo <= up:
if nums[mi] == target:
return mi
elif nums[mi] > target:
up = mi - 1
else:
lo = mi + 1
mi = (lo + up) // 2
return lo
``````

(電腦科學領域的對數一般不特別提的話通常是以2為底)

(因為0取負號還是0)

Binary Search是在排序陣列或一些有序的資料結構中很常用到的演算法，

「(Java)如果上限接近Integer.MAX_VALUE的話相加有overflow的可能？」
(將(lo+up)/2改成lo + (up-lo)/2，可以保證不會溢出)

「時間/空間複雜度？」
(O(logN), O(1))

「我想知道到底結果target是否存在array中，但不想額外加回傳的值？」
(如上面提到的，將插入的狀況改為**-index-1**來表達)

0053. Maximum Subarray (Easy)

### 1 則留言

0
hyj1116
iT邦新手 4 級 ‧ 2019-10-03 23:27:36

Desolve iT邦新手 5 級 ‧ 2019-10-04 00:51:29 檢舉

hyj1116 iT邦新手 4 級 ‧ 2019-10-04 23:27:52 檢舉

Desolve iT邦新手 5 級 ‧ 2019-10-07 08:39:45 檢舉