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& nums, int target) { int left = 0, right = nums.size() - 1;//确定区间范围,且为左闭右闭 while(left <= right)//当left == right时依然有意义,因此为> 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& nums, int target) { int left = 0, right = nums.size(); while(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)