【算法学习笔记】二分查找法

二分查找法

二分查找的本质就是分治法，小时候有过这么一种猜数字的游戏，你在心中想一个大于0小于100的数字，然后我来提问，你只用回答是或者不是，比如“你想的数字比50大吗” 你说不是，那么就将范围缩小到0-50，反之范围就在50-100；
就这样逐步询问，最终总能猜到你心里想的数字，并且每次都以范围一半的值作为提问的参考值的话，你相对提问的次数是最少的，也就是提问的最优解；这就是二分法

二分查找发的基本思想

将n个元素分成大致相等的两部分，取a[n/2] （ a[]是数组，n/2是数组索引）与目标元素target作比较

• 如果target = a[n/2],那这就是要找的元素
• 如果target < a[n/2],继续搜索，搜索范围缩小到数组a的左半部分
• 如果target > a[a/2]，继续搜索，搜索范围缩小到数组a的右半部分

二分查找的时间复杂度

• 因为循环时一层，所以有n个元素时间复杂度就是循环的次数k，n=>n/2=>n/4…=>n/2^k。
• n足够大的时候极限n/2^k趋近与1
• k = log2n
• 时间复杂度为O(n) = O(log2n) 或者O(n) = O(logn)

实现

class Solution{
    public:
    int search (vecter<int>& nums,int target){
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right){
            int mid =  left + (right-left)/2;
            if(nums[mid] == target){
                return mid;
            } 
            else if(nums[mid] > target){
                right = mid -1;
            }
            else if(nums[mid] < target){
                left = mid -1;
            }
        }
        return -1;
    }
}

• 这里有几个细节
  • 循环的终止条件用的是小于等于 while (left <= right)，因为只是小于的时候回漏掉等于的情况就是[2,2]这种情况回终止循环返回-1；
  • 还有就是在计算这个

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

的时候 我们可以用left + ((right -left) >> 1 位运算提升性能；