本文共 3712 字，大约阅读时间需要 12 分钟。

转载请注明：

二分查找的应用

二分查找作为 O(log(n)) 时间复杂度的查找算法得到了广泛的使用。

1.在已排序的数组中查找特定的元素。或者是满足条件的第一个元素 
2.数学常用的求解方程的解，也是数学家所指的对半查找。 
3.程序调试中用来定位错误语句 
4….

二分查找的原始代码

   int binarySearch(int A[],int left,int right,int target)   {        int mid;        while(left<=right)        {         mid=(left+right)/2;         if(A[mid]
    
     left=
     mid+
     1;         
     else 
     if(A[
     mid]==target)             return 
     mid;         
     else             
     right=
     mid-
     1;        }        return -
     1;   }
    
   
    
1
    
2
    
3
    
4
    
5
    
6
    
7
    
8
    
9
    
10
    
11
    
12
    
13
    
14
    
15
   

注意事项 一：mid溢出

针对上文代码中

mid=(left+right)/2;
   
    
1
   

这一句代码有两个注意事项：

1.计算机方式有乘以 2n 或者是除以 2n 都可以利用移位代替。所以上述代码可以改为：

mid=(left+right)>>1;
   
    
1
   

2.第二个需要注意的是该段代码有可能产生溢出。当数组的中元素个数很多时候，至少大于 INT_MAX2 ,当left和right都是接近INT_MAX.二者相加就可能得到一个负数。这种办法有两个。

2.1将mid定义成

long long mid;
     
      
1
     

2.2

mid=left+(right-left)>>1;
     
      
1
     

注意事项 二：常数步的前进

这个错误在编程珠玑中也有提到的，但是自己还是经常放错误。 
还是原来的那段代码很多人容易写成

   int binarySearch(int A[],int left,int right,int target)   {        int mid;        while(left<=right)        {         mid=(left+right)/2;         if(A[mid]
    
     left=
     mid;         
     else 
     if(A[
     mid]==target)             return 
     mid;         
     else             
     right=
     mid;        }        return -
     1;   }
    
   
    
1
    
2
    
3
    
4
    
5
    
6
    
7
    
8
    
9
    
10
    
11
    
12
    
13
    
14
    
15
   

很多人在这时候可以很清楚的意识到上述中

            left=mid+1     ==》   left=mid;            right=mid-1    ==》   right=mid;
   
    
1
    
2
    
3
    
4
    
5
   

此处得特别注意是这样很容易掉入陷阱当中 
比如当

LeetCode实例

这里在leetcode上找了一个应用来说明问题 
链接地址 
题目： 
Follow up for “Find Minimum in Rotated Sorted Array”: 
What if duplicates are allowed?

Would this affect the run-time complexity? How and why? 
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

class Solution {public:    int findMin(vector<int>& nums) {               if(nums.empty())            return 0;        int left=0,right=nums.size()-1,mid;        while(nums[left]>=nums[right])        {            mid=(left+right)>>1;            if(nums[mid]>nums[right])                left=mid+1;            else if(nums[left]>nums[mid])                right=mid;            else if(nums[left]==nums[mid]&&nums[right]==nums[mid])            {                int tmp=nums[left];                for(int i=left;i<right;i++)                if(tmp>nums[i])                  tmp=nums[i];                return tmp;            }        }        return nums[left];    }};
   
    
1
    
2
    
3
    
4
    
5
    
6
    
7
    
8
    
9
    
10
    
11
    
12
    
13
    
14
    
15
    
16
    
17
    
18
    
19
    
20
    
21
    
22
    
23
    
24
    
25
   

本人在写上述代码时候就是放了第二个错误。

                left=mid+1;                right=mid;
   
    
1
    
2
    
3
    
4
    
5
   

只要有一个常数步就可以在邻近的两个元素避免死循环。 
第二道二分查找题目 
Sqrt(x) Total Accepted: 55059 Total Submissions: 238405 My Submissions Question Solution  
Implement int sqrt(int x).

Compute and return the square root of x

class Solution {public:    int mySqrt(int x) {       int left=0;       int right=x;       long long  mid;       while(left<=right)       {              mid=(left+right)/2;          if(mid*mid
    
     left=
     mid+
     1;           
     else 
     if(
     mid*
     mid>x)           
     right=
     mid-
     1;           
     else            return 
     mid;       }       
     if(
     left*
     left>x)       return 
     left-
     1;       return 
     left;    }};