704. Binary Search
(https://leetcode.cn/problems/binary-search/)
思路
-
二分法前提：
- 有序陣列
- 陣列內元素不重復
-
易錯點：二分法的邊界條件，如究竟是 while(left < right) ，還是 while(left <= right) ；究竟是 right == middle，還是 right == middle -1
-
因此為了寫好二分法，我們需要首先想清楚對區間如何定義的，而區間的定義正是不變數，每次進行while查找時邊界的處理都必須根據區間定義
左閉右閉寫法
- 區間如何定義區分了我們如何寫二分法，也就是 [left,right]：
- 因為left == right此條件是有意義的，因此while(left <= right)
- **if ( nums[middle] > target ) **中，right 應賦值為 middle - 1
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; //確定區間范圍，且為左閉右閉
while(left <= right) //當left == right時依然有意義，因此為<=
{
int mid = left + ((right - left) >> 1); //以防溢位.若為(left+ right) >> 1，則可能會溢位
//target在左區間
if(nums[mid] > target)
{
right = mid - 1;
continue;
}
//target在右區間
else if(nums[mid] < target)
{
left = mid + 1;
continue;
}
//找到目標值
else
{
return mid;
}
}
//未找到目標值
return -1;
}
};
左閉右開寫法
- [left，right)：
- 因為在區間[left，right)中，left == right沒有意義，因此為while ( left < right )
- 在if ( nums[middle] > target )中，因為是右開，此時right應賦值為middle，此時下個區間不會比較nums[middle]
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while(left < right)
{
int mid = left + ((right - left) >> 1);
if(nums[mid] > target)
{
right = mid;
continue;
}
else if(nums[mid] < target)
{
left = mid + 1;
continue;
}
else
{
return mid;
}
}
return -1;
}
};
時間復雜度：O(logn)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513030.html
標籤：其他
上一篇：leetcode 236. Lowest Common Ancestor of a Binary Tree 二叉樹的最近公共祖先(中等)