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)