## 704. Binary Search(Easy)

:::spoiler 題目描述
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.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

$1 <= nums.length <= 10^4$
$-10^4 < nums[i], target < 10^4$
All the integers in nums are unique.
nums is sorted in ascending order.
:::

:::spoiler 解題思路
1. 最左邊的點為index_L，最右邊的點為index_R，知道陣列長度後，抓正中間的點作為index_M
2. 判斷target在哪一區間，
* 若target小於index_L，則代表找不到，回傳-1
* 若target大於index_R，則代表找不到，回傳-1
* 若target等於index_L、index_M、index_R任一，則代表找到了，回傳其index
* 若以上皆非，代表其職介於 index_L及index_M 或 index_M及index_R，縮小範圍重新找一次
* 若最後還是找不到，當(index_L+index_R)/2 == index_L時，代表此範圍中沒有該數值，回傳-1
:::

:::spoiler 程式碼

int search(int* nums, int numsSize, int target){
    int index_L = 0;
    int index_R = numsSize - 1;
    int index_M = (index_L + index_R) / 2;
   
    while(1)
    {
        if(target < nums[index_L])
        {
            return -1;
        }
        else if(target == nums[index_L])
        {
            return index_L;
        }
        else if(target < nums[index_M])
        {
            index_R = index_M - 1;
        }
        else if(target == nums[index_M])
        {
            return index_M;
        }
        else if(target < nums[index_R])
        {
            index_L = index_M + 1;
        }
        else if(target == nums[index_R])
        {
            return index_R;
        }
        else
        {
            return -1;
        }

        // Check if there is only one integer in sums
        if(index_L == index_M)
        {
            return -1;
        }

        index_M = (index_L + index_R) / 2;
    }
}

:::

:::spoiler 時間/空間複雜度
* 時間複雜度: $O(logn)$
* 空間複雜度: $O(1)$
:::