【LeetCode】704. Binary Search

Question link

Link

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;
}