1. 有时HashMap,HashSet能帮助我们处理一些无序数组的问题
  2. 排序后考虑下重复问题

二分搜索

普通

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

搜索左侧边界

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

搜索右侧边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int binartSearch(int[] nums,int target){
    if(nums.length == 0) {
        return  -1;
    }
    int left = 0;
    int right = nums.length;
    while (left < right){
        int mid = left + (right - left)/2;
        if(nums[mid] == target){
            left = mid + 1;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    //注意最后终止时为left == right,right侧为开区间,因此要减1.
    if(nums[right - 1] != target){
        return  -1;
    }
    return right - 1;
}

抽象二分搜索

1、确定 x, f(x), target 分别是什么，并写出函数 f 的代码。

2、找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。

3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

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
// 函数 f 是关于自变量 x 的单调函数
int f(int x) {
    // ...
}

// 主函数，在 f(x) == target 的约束下求 x 的最值
int solution(int[] nums, int target) {
    if (nums.length == 0) return -1;
    // 问自己：自变量 x 的最小值是多少？
    int left = ...;
    // 问自己：自变量 x 的最大值是多少？
    int right = ... + 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(mid) == target) {
            // 问自己：题目是求左边界还是右边界？
            // ...
        } else if (f(mid) < target) {
            // 问自己：怎么让 f(x) 大一点？
            // ...
        } else if (f(mid) > target) {
            // 问自己：怎么让 f(x) 小一点？
            // ...
        }
    }
    return left;