二分法

二分法是一种能极大节省查找时间复杂度的算法，使用条件：

  1. 数组为有序数组
  2. 数组中没有重复元素

Leetcode 例题

二分查找

二分查找此类题目 关键点在于找对区间，找好临界值点，可分为两种情况

区间为左闭右闭类型

此时 ``while left <= right`` 需要取等，因为此时相等时的mid值有意义可以取到，当``nums[mid]>target``时·，``right = mid-1``，因为此时mid下标所指的值一定不等于target所以可以往前再移一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        
        while(left <= right)
        {
            int mid = (left + right) / 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`` 需要取等，因为此时相等时的mid值没有意义，当``nums[mid] > target``时·，``right = mid``，这样在下一次比较中，因为右区间为开，mid会被排除在查找区间外

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        
        while(left < right)
        {
            int mid = (left + right) / 2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid] > target)
            {
                right = mid;
            }
            else if(nums[mid] < target)
            {
                left = mid +1;

            }
        }
        return -1;
    }
}

区间为开区间

循环判断条件 left+1 < right, 区间范围为（left , right）。

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
class solution{
    // lowerBound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.length
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

     public int lowerBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        // left 和 right 都取不到。
        while(left+1 < right){
            int mid = left + (right - left)/2;

            if(nums[mid] >= target)
                right = mid; // （left,mid）
            else
                left =mid; // （mid,right）
          
        }
        
        // 循环结束后 left+1 = right
        // 此时 nums[left] < target 而 nums[right] >= target
        // 所以 right 就是第一个 >= target 的元素下标
        return right;
    }
}