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

## Leetcode 704. Binary Search — Python


### 題目敘述：

一個從小到大排序好的 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


### 題目敘述：
要刪除某個元素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