2、二分法

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

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

2.1 Leetcode 例题

二分查找

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

1. 区间为左闭右闭类型

此时 ``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;
    }
}

2. 区间为左闭右开类型

此时 ``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;
    }
}