# 【LeetCode】704. Binary Search

## Question link
[Link](https://leetcode.com/problems/binary-search/description/)

## Intuition
>Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`.
You must write an algorithm with `O(log n)` runtime complexity.
給定一個整數陣列，以升序排列，並給定一個`target`整數，請撰寫一個函數尋找`targets`在整數陣列的索引位置，如果沒有找到就回傳`-1`，演算法要求時間複雜度必須 `O(log n)`

題目就是希望我們使用二分搜尋來找到相對應的目標，如果看到題目為是**有序陣列**以及**無重複元素**的話，基本上就是用二分搜尋來解題了，二分收尋最重要的就是**邊界條件**的處理，邊界分為四種
1. 左閉右閉 $[a, b]$
2. 左閉右開 $[a, b)$
3. 左開右閉 $(a, b]$
4. 左開右開 $(a, b)$

大部分都使用左閉右開或左閉右閉，當在進行二分搜尋時，需要檢查的是邊界部分是否有意義?以及保持**迴圈不變量原則**處理
* 如果定義target是在 $[a, b]$ 的區間當中則
* `while(left <= right)`，需要使用`<=`，因為`left == right` 是有意義的
* `if (nums[mid] > target)` 的時候，`mid = left -1 `，因為當前`mid`位置一定不是`target`，因此我們的區間必須遵循原則，移動到`left = mid - 1`
* 如果定義target是在 $[a, b)$ 的區間當中則
* `while(left < right)` ，需要使用 `<`，因為當`left == right`時是有可能超出邊界的
* `if (nums[mid] > target)` 的時候，`mid = left`，因為當前`mid`位置一定不是`target`，而遵循區間的原則，`left = mid`

## Approach

1. 宣告左右兩個區間的索引 `l` 與 `r` (左閉右閉)
2. 遍歷陣列直到 `l <= r`
* 宣告中間索引`mid = (left + right) / 2`
* 檢查中間位置的值是否等於目標
* 是則直接回傳位置
* 檢查中間位置的值是否小於目標
* 是則移動`l`至`mid + 1`
* 否則移動`r`至`mid - 1`
3. 未找到目標值直接回傳

## Complexity
- Time complexity: $O(\log n)$
- Space complexity: $O(1)$

## Code

int search(int* nums, int numsSize, int target) {
    int l = 0;
    int r = numsSize - 1;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] == target){
            return mid;
        }
        else if (nums[mid] < target){
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    return -1;
}

int search(int* nums, int numsSize, int target) {
    int l = 0;
    int r = numsSize;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] == target){
            return mid;
        }
        else if (nums[mid] < target){
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    return -1;
}