# Python 實作 Binary Search

>以下提供兩種不同情況以及Unit Test

## 第一種作法
### 單純尋找特定元素在一以排序陣列中
假設我們有一個以排序陣列 `nums = [1,3,5,7,9,11,13,15]` 和要尋找的目標 `target = 11`，如果`target`存在於`nums`中，返回該索引位置，否則返回`-1`

#### 程式碼

def BS(nums,target):
    if target not in nums:
            return -1
    else:
        return nums.index(target)

## 第二種做法
### 尋找特定元素在一以排序陣列中的索引位置，如果不存在索引位置即返回元素可插入位置

假設我們有一個以排序陣列 `nums = [2,4,6,8,10,12,14,16]` 和要尋找的目標 `target = 3`，如果`target`存在於`nums`中，返回該索引位置，否則返回可以插入元素的位置`1`

#### 程式碼

def BS(nums:list,target:int) -> int:
    if target in nums:
        return nums.index(target)
    f = 0
    r = len(nums)-1
    while r >= f:
        mid = (f+r)//2
        if target == nums[mid]:
            return nums.index(mid)
        if nums[mid] > target:
            r = mid-1
        if nums[mid] < target:
            f = mid+1
    return f

## 測試
以下提供該測試程式，可套用上述兩種狀況

test = [[1,3,5,7,9,11,13,15],[2,4,6,8,10,12,14,16]]
tar = [11,3]
out = [5,1]

for idx in range(len(test)):
    try:
        result = BS(test[idx],tar[idx])
        if result == out[idx]:
            print(f'case: {idx+1} pass!')
        else:
            print(f'case: {idx+1} fail!')
    except Exception as ex:
        print(f'we got some error, here is error msg: {ex}')