基本搜尋演算法 二分搜尋法 Binary Search_Leetcode 704

這題的題目在這:

題目會給我們一個排序好的陣列，還有一個目標值target

要求我們在陣列中尋找target所在的索引位置。
如果target 不存在，返回-1

題目要求必須在O( log n )對數時間內完成 。

測試範例:

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 <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

演算法:

其實各家課本或教材都大同小異，都是從剖半找中心點的方式去搜索。

如果中心點 = target，代表已經找到了，就返回中心點。

如果中心點 < target，代表現在的值還太小，就收縮左邊界，往右邊尋找。

如果中心點 > target，代表現在的值還太大，就收縮右邊界，往左邊尋找。

如果最後找不到，就返回-1

但是有幾個小細節要留意:

1. 中心點尋找時，使用比較安全的計算方式，
   中心點 = 左端點 + (右端點-左端點) 除以 2，避免overflow

尤其是靜態型別語言，例如C, C++的同學要特別留意。

mid = left + (right - left ) // 2

2. 可以額外做一個小優化optimization，當target已經落在搜尋範圍[left, right]之外時，提早終止不必要的搜尋分支。

　　　if not (nums[left] <= target <= nums[right]):
　　　　# optimization, early stop unnecessary branch
　　　　return-1

程式碼:

Iterative method 迭代法:

class Solution:
　def search(self, nums: List[int], target: int) -> int:

　　left, right = 0,len(nums)-1

　　while left <= right:

　　　if not (nums[left] <= target <= nums[right]):
　　　　# optimization, early stop unnecessary branch
　　　　return-1

　　　mid = left + ( right - left ) // 2

　　　if( nums[mid] == target):
　　　　return mid

　　　elif nums[mid] < target:
　　　　left = mid+1
　　　
　　　else:
　　　　right = mid-1

　　return -1

Recursive method 遞迴法:

class Solution:
　def search(self, nums: List[int], target: int) -> int:
　　
　　def binary_search(nums, left, right, target ):
　　　
　　　if left > right:
　　　　# base case:
　　　　# miss
　　　　# target does not exist in input array
　　　　return -1

　　　if not (nums[left] <= target <= nums[right]):
　　　　# optimization, early stop unnecessary branch
　　　　return -1　　　

			# update index of mid point
　　　mid = left + (right-left)//2

　　　if nums[mid] == target:

　　　　# base case:
　　　　# hit
　　　　return mid

　　　if target > nums[mid]:
　　　　
　　　　# search target in right half
　　　　return binary_search(nums, mid+1, right, target)

　　　else:

　　　　# search target in left half
　　　　return binary_search(nums, left, mid-1, target)

　　#---------------------------
　　return binary_search(nums, 0, len(nums)-1, target)

時間複雜度:

O( log n ) , 可以從 T(n) = T(n/2) + O(1) 用Master Theorem推導而來

空間複雜度:

迭代法為O(1)，相當於指使用雙指針double pointers，所耗費的空間成本固定，為常數級別O(1)

遞迴法為O( log n)，成本來自於recursion call stack depth 遞迴呼叫堆疊深度

Reference:

[1] Python/JS/Go/C++ log( n ) sol. by divide-and-conquer. [ With explanation ] - Binary Search - LeetCode