二分法

二分法概述

    什么是二分法呢？相信大家都有所了解，举个最经典的二分的例子。

​ 给定一个整型有序数组，和一个值$value$，如果$value$在数组中，返回true否则返回false。由于数据状态的特殊性，并不需要遍历数组求解，只需要每次找到数组的中间位置mid，和value相比较，如果$>value$则说明mid位置和mid位置右边的数据都不符合要求，故而更新$r=mid-1$,反之则更新$l=mid+1$。这里给出两套边界条件，请自行筛选。

// 1	
public static boolean exist(int[] arr, int num) {
    if (sortedArr == null || sortedArr.length == 0) {
        	return false;
    }
    int l = 0;
    int r = arr.length - 1;
    int mid = 0;
    // l == r 时结束，剩下最后一个数
    while (l < 4) { 
        mid = l + ((r - l) >> 1); // 等价于 (l + r) / 2 ,防止溢出
        if (arr[mid] == num) {
           return true;
        } else if (arr[mid] >rnum) {
           r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return arr[l] == num;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 2
public static boolean exist(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int l = 0;
        int r = arr.length - 1;
        int mid = 0;
        // L == R 时结束，剩下最后一个数
        while (l < r) {
            mid = l + ((r - l) >> 1);// 等价于 (l + r) / 2 ,防止溢出
            if (arr[mid] >= num) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return arr[l] == num;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    这个流程并不复杂，难得是边界条件的确定，这个就需要读者自行调试（$Debug$）理解。此处算法的时间复杂度为$O(logN)$，空间复杂度$O(1)$。

二分 >= value最左的位置

    自行完成，这里仅提供参考代码。

    public static int nearLeftIndex(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        int mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (arr[mid] >= value) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return arr[l] < value ? -1 : l;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二分 <= value最右的位置

    自行完成，这里仅提供参考代码。

 public static int nearRightIndex(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int l = 0;
        int r = arr.length - 1;
        int mid;
        while (l < r) {
            mid = l + r + 1 >> 1;
            if (arr[mid] <= value) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return arr[l] > value ? -1 : l;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    相信做完这两道题你对二分的理解也更近了一步，那么接下来综合这两道练习题，请完成leetcode32题，这道题是对这两道练习题的综合，可以帮助你更好的掌握二分法，同时二分的写法也有多种，请选择适合自己的边界条件。

局部最小值问题

定义局部最小值：局部最小值是指其值严格小于左右相邻元素的值，给你一个整数数组 nums，找到局部最小值元素并返回其索引。数组可能包含多个局部最小值，在这种情况下，返回 任何一个局部最小值 所在位置即可。

• 你可以认为$nums[-1]=+\infty ，nums[n]=+\infty$

• 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

• $nums[i]!=nums[i+1]$

• $n$为数组长度

    此题由于数据状况特殊，题目局部最小值的定义特殊，所以我们可以使用二分法进行求解。首先我们要先知道$nums[-1]=+\infty ，nums[n]=+\infty$，也就是数组左侧是下降的,并且右侧也是下降(U型)，而且相邻元素之间不相等，这就很特殊了，保证了数组之中一定有局部最小值，并且可以二分。如果$nums[mid]<nums[mid+1]$则左边会存在局部最小值去掉右边（$r=mid$），如果$nums[mid]>nums[mid+1]$则右边会存在局部最小值去掉左边（$l=mid-1$）。

  public static int getLessIndex(int[] arr) {
      if (arr == null || arr.length == 0) {
          return -1; // no exist
      }
      if (arr.length == 1 || arr[0] < arr[1]) {
          return 0;
      }
      if (arr[arr.length - 1] < arr[arr.length - 2]) {
          return arr.length - 1;
      }
      int l = 1;
      int r = arr.length - 2;
      int mid = 0;
      while (l < r) {
          mid = l + r >> 1;
          if (arr[mid] >= arr[mid + 1]) {
              l = mid + 1;
          } else {
              r = mid;
          }
      }
      return l;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    请完成162. 寻找峰值，如果本篇文章对你有帮助，请点赞、评论、转发，你的支持是我创作的动力！！！