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)