---
# System prepended metadata

title: 代码随想录算法训练营第一天 | 704. Binary Search & 27. Remove Element

---

# 代码随想录算法训练营第一天 | 704. Binary Search & 27. Remove Element



## Leetcode 704. Binary Search — Python

![](https://hackmd.io/_uploads/rknuMYTL3.png)

### 題目敘述：

一個從小到大排序好的 input array，給定一個target，請寫出一個function來找藏在array裡的target，需要O(logn)

### 思考：

keyword -> ==sorted== + ==logn== -> <font color="#f00">Binary Search</font>

### Time and Space Complexity
**T: O(logn)**
**S:O(1)**

```
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1 # 定義target在[left, right]
        while l <= r:
            mid = (r+l)//2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid
        return -1

```


## 27. Remove Element

![](https://hackmd.io/_uploads/B1-BLY6U2.png)

### 題目敘述：
要刪除某個元素val。return 沒有給定val的array

### 思考：

思考array特殊結構，如果要刪除某個元素，必須把要刪除的元素遞補過去，因為array屬性是連續性的，不被破壞
使用快慢指針， 快指針負責找不是val的值（如果遇到val就繼續前進）
慢指針等快指針找到非val值就把當前慢指針的值取代，再前進

### Time and Space Complexity
**T: O(n)**
**S:O(1)**


```
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (r+l)//2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid
        return -1
```