算法学习笔记（三）二分法查找(Binary Search)的应用

发表于 | 分类于 | 阅读次数：
本文字数： 5.2k | 阅读时长 ≈ 5 分钟
二分法查找的应用

二分法是把元素分为“存在”和“不存在”两部分，不断去掉“不存在”的部分，最终找到满足要求的元素。常见的二分法用于在排序好的元素中查找某个值，每次去除一半，效率较高。但是，不一定只在这类有序状态下才能使用二分，如果能够构建标准，判断两侧是否有需要的元素，并可以不断去除“不存在”的部分，就也可以用二分法来解决。下面通过几个实例加深对二分法的理解。

这里先补充回顾几个位运算符的知识点：

右移”>>“：带符号右移，左侧用符号来补位。如果 a>>1，表示a带符号右移一位，得到的结果相当于a/2。

无符号右移”>>>“: 不管符号，左侧一律用0来补位。

左移”<<“：左移只有这个符号，用0补位。 如果a<<1，得到的结果相当于a*2。

取两个数中间值的方法：int mid = (left + right)/2; 但这种方法left+right有可能溢出。int mid = left + (right - left)/2; 这种方法可以防止溢出，但是算术运算比位运算要慢。因此结合上面回顾的知识点，较好的写法为：

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

（1） 在一个有序数组中，找某个数是否存在

假设数组中的数从小到大排列。先确定数组中元素的中间位置，如果等于要找的数，就直接返回；如果小于要找的数，就说明要找的数在中间位置的右侧，直接忽略掉左侧的内容，找右侧的中间位置，重复此过程，直至找到该元素（存在）或者排除掉所有元素（不存在）。因为每次都能去掉一半的内容，时间复杂度为O(log2N)，简写为O(logN)，默认以2为底，它优于O(N)的直接遍历。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean isExist(int[] arr, int num) {
    if(arr==null || arr.length==0) {
        return false;
    }
    int left = 0;
    int right = arr.length - 1;
    int mid = 0;
    while(right > left) {
        mid = left + ((right - left)>>1);
        if(arr[mid] == num) {
            return true;
        }else if(arr[mid] > num) {
            right = mid - 1;
        }else {
            left = mid + 1;
        }
    }
    return arr[left] == num;
}

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function isExist(arr,num){
      if(arr==null || arr.length===0){
        return false;
      }
      var left = 0;
      var right = arr.length - 1;
      var mid = 0;
      while(right > left){
        mid = left + ((right-left)>>1);
        if(arr[mid] === num){
          return true;
        }else if(arr[mid] > num){
          right = mid - 1;
        }else{
          left = mid + 1;
        }
      }
      return arr[left] === num;
    }

（2）在一个有序数组中，找到大于等于某个数的最左侧位置

假设数组中的数从小到大排列。与上个问题类似，先确定中间位置，看是否满足大于等于该数，如果满足就看左半部分，找左半部分的中间位置；反之忽略左半部分看右部，重复此过程。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int nearestIndex(int[] arr, int num) {
       if(arr==null || arr[arr.length-1]<num) {
           return -1;
       }
       int left = 0;
       int right = arr.length - 1;
       while(right > left) {
           int mid = left + ((right - left)>>1);
           if(arr[mid] >= num) {
               right = mid;
           }else {
               left = mid + 1;
           }
       }
       return left;
   }

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function nearestIndex(arr,num){
   if(arr==null || arr[arr.length-1]<num){
     return -1;
   }
   var left = 0;
   var right = arr.length - 1;
   var mid = 0;
   while(right > left){
     mid = left + ((right - left)>>1);
     if(arr[mid] >= num){
       right = mid;
     }else{
       left = mid + 1;
     }
   }
   return left;
 }

（3）局部最小值问题（长度为n的无序数组，任何相邻的数不相等）

要求在数组中找到一个局部最小值并返回该位置。首先，判断两端的值。如果arr[0] < arr[1]，那么arr[0]就是局部最小值；如果不满足，查看是否arr[n-1] < arr[n-2]，这样arr[n-1]就是局部最小；如果两端的值都不是局部最小值，那么说明必存在中间位置的局部最小值arr[i-1] > arr[i] < arr[i+1]（因为头部呈现递减，尾部呈现递增，不可能不存在局部最小）。找中间位置，判断它是否是局部最小，如果不是并且这个局部显示递增，那么就忽略中间位置的右半部分，在它的左侧找局部最小值，反之显示递减就找右侧（和刚才原理相同，头部呈现递减尾部呈现递增那么其中一定存在局部最小值，因此又能一次去除一半的数据）。最终找到并返回该位置。

在这个例子中，数组内的数并不是有序排列的，但还是可以构建出一个每次去除一半元素的标准，所以二分法在此适用。

Java

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
26
27
public static int getMinIndex(int[] arr) {
        int index = 0;
        if(arr==null || arr.length==0) {
            index = -1;
        }else if(arr.length==1 || arr[0]<arr[1]) {
            index = 0;
        }else if(arr[arr.length-1] < arr[arr.length-2]) {
            index = arr.length - 1;
        }else {
            int left = 0;
            int right = arr.length - 1;
            int mid = 0;
            while(left < right) {
                mid = left + ((right - left)>>1);
                if(arr[mid]<arr[mid+1] && arr[mid]<arr[mid-1]) {
                    index = mid;
                    break;
                }else if(arr[mid] > arr[mid+1]) {
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
                index = left;
            }
        }
        return index;
    }

JavaScript

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
26
27
function getMinIndex(arr){
     var index = 0;
     if(arr==null || arr.length===0){
       index = -1;
     }else if(arr.length===1 || arr[0]<arr[1]){
       index = 0;
     }else if(arr[arr.length-1]<arr[arr.length-2]){
       index = arr.length - 1;
     }else{
       var left = 0;
       var right = arr.length - 1;
       var mid = 0;
       while (left < right) {
         mid = left + ((right - left) >> 1);
         if(arr[mid]<arr[mid-1] && arr[mid]<arr[mid+1]){
           index = mid;
           break;
         }else if(arr[mid] > arr[mid-1]){
           right = mid - 1;
         }else{
           left = mid + 1;
         }
         index = left;
       }
     }
     return index;
   }