Keep moving forward

0%

Binary Search

Posted on Edited on In

本文将对二分查找算法进行详细的归纳，并对LeetCode上出现的一些相关的题目进行归纳。

什么是二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。举个例子，当我们猜一件衣服的价格，如果被告知价格区间在500到1000之间，我们第一次可能会猜价格为750，如果750低了，我们会往比750高的价格猜，比如875，如果875高了，我们下一次猜的价格就可以是（750 + 875）/ 2 = 812，依次猜下去，直到猜到正确价格。

二分查找的时间复杂度是O(logn), 因为每次查找后数据区间都会缩小为原来的一半，所以二分查找是一种十分高效的查找算法。有时候比O(1)的算法还要高效。因为有些O(1)的算法可能表示的是一个非常大的常数值。

一个最简单的二分查找

最简单的二分查找算法就是针对不存在重复元素的有序数组。以下给出其递归实现和非递归实现的Java代码。

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int bsearch(int[] a, int n, int value) {
	int low = 0;
	int high = n - 1;
	while(low < = high) {
		int mid = (low + high) / 2;
		if(a[mid] == value) {
			return mid;
		}else if(a[mid] < value) {
			low = mid + 1;
		}else {
			high = mid - 1;
		}
	}

	return -1;
}

上述代码要注意的地方

  1. 循环退出条件

这里的循环退出条件是low <= high, 而不是low < high。如果写 low < high, 举个例子，当 a = [2, 4, 5, 6, 7, 8, 9], value = 2时，刚开始low = 0, high = 6, mid = 3, 由于 a[3] = 6 > value, high 更新为 3 - 1 = 2, mid 更新为 （2 + 0）/ 2 = 1, 由于a[1] = 4 > value, 所以 high 更新为 1 - 1 = 0， 此时如果循环退出条件是 low < high, 那么 a[0] = 2 就没有被检查到。

  1. mid的取值

mid = (low + high) / 2 这种写法其实并不是很好，如果low和high都比较大的时候，两者之和可能会溢出，这里可以改进写法为 mid = low + ((high - low) >> 1); 因为计算机处理位运算要更比除法运算更快一点。

  1. low = mid + 1 & high = mid - 1;

如果代码中直接写 low = mid 或者 high = mid， 可能会发生死循环，比如，high = low = 3, 而且 a[3] != value，low和high就会一直等于3，这样就会导致循环无法退出。

递归实现

和非递归实现差不多，递归实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
    return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
    if (low > high) return -1;

    int mid =  low + ((high - low) >> 1);
    if (a[mid] == value) {
        return mid;
    } else if (a[mid] < value) {
        return bsearchInternally(a, mid+1, high, value);
    } else {
        return bsearchInternally(a, low, mid-1, value);
    }
}

二分查找的适用情况

虽然二分查找算法的时间复杂度是O(logn), 但是二分查找只适合在一定的场景下使用。

  • 二分查找依赖的顺序表结构

针对java，就是数组，或者基于数组的容器ArrayList,因为二分查找需要按照下标随机访问元素，如果二分查找依赖的是其他数据结构，比如链表，链表访问一个元素需要traverse the whole list，其时间复杂度是O(n)，数据如果用链表存储，其对应的二分查找的时间复杂度会非常高。

  • 二分查找针对的是有序数组

数据必须是有序的，如果数据是无须的，要使用二分查找之前我们还需要先排序，而排序的时间度最低是O(nlogn)，所以对于我们要使用的数据，最好没有频繁的插入和删除操作，如果有，每次插入和删除操作之后，由于还需要排序，其时间复杂度会比较高。

  • 数据量太小不适合二分查找

数据量太小，直接顺序遍历就好，比如 n = 10 时。数据量比较大，二分查找的优势才会比较明显。

不过，这里有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，我都推荐使用二分查找。比如，数组中存储的都是长度超过 300 的字符串，如此长的两个字符串之间比对大小，就会非常耗时。我们需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势。

  • 数据量太大也不适合二分查找

二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。如果我们没有那么大的连续内存空间，那么就不适合用二分查找。

二分查找的变形题目

二分查找有许多变形题目，本文将归纳一些常见的二分查找变形题目。

变形1: 查找第一个值等于给定值的元素

直接上代码，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == 0) || (a[mid - 1] != value)) return mid;
            else high = mid - 1;
        }
    }
    return -1; // if not finding value in a, return -1.
}

对上述代码的解释如下：

a[mid] 跟要查找的 value 的大小关系有三种情况：大于、小于、等于。对于 a[mid]>value 的情况，我们需要更新 high= mid-1；对于 a[mid]< value 的情况，我们需要更新low=mid+1。 这两点都很好理解。那当 a[mid]=value 的时候应该如何处理呢？如果我们查找的是任意一个值等于给定值的元素，当 a[mid] 等于要查找的值时，a[mid] 就是我们要找的元素。但是，如果我们求解的是第一个值等于给定值的元素，当a[mid] 等于要查找的值时，我们就需要确认一下这个 a[mid] 是不是第一个值等于给定值的元素。我们重点看第 11 行代码。如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；如果 mid 不等于 0，但 a[mid] 的前一个元素 a[mid-1] 不等于 value，那也说明 a[mid] 就是我们要找的第一个值等于给定值的元素。如果经过检查之后发现 a[mid] 前面的一个元素 a[mid-1] 也等于 value，那说明此时的 a[mid] 肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新high = mid-1，因为要找的元素肯定出现在 [low, mid-1] 之间。

变形2： 查找最后一个值等于给定值的元素

和变形1原理类似，这里直接贴代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
            else low = mid + 1;
        }
    }
    return -1;
}

变形3: 查找第一个大于等于给定值的元素

变形3和变形1、2略微有点点不同，但整体还是差不多的，这里也直接贴代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int bsearch(int[] a, int n, int value) {
	int low =  0;
	int high = n - 1;
	while(low <= high>) {
		int mid = low + ((high - low) >> 1);
		if(a[mid] < value) {
			low = mid + 1;
		}else {
			if(mid == 0 || a[mid-1] < value) return mid;
			else high = mid  - 1;
		}
	}
	return -1;
}

变形4: 查找最后一个小于等于给定值的元素

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int bsearch(int[] a, int n, int value) {
	int low = 0;
	int high = n - 1;
	while(low <= high) {
		int mid = low + ((high - low) >> 1);
		if(a[mid] > value) {
			high = mid - 1;
		}else {
			if(mid == n-1 || a[mid + 1] > value) return mid;
			else low = mid + 1;
		}
	}
	return -1;
}

LeetCode上相关的题目

  • 704
  • 35
  • 981

下面四道题目全针对rotated sorted array

  • 33
  • 81
  • 153
  • 154

最基本的二分查找题目

  1. Binary Search

704的衍生题

  1. Search Insert Position

这题表明二分查找一个特点：如果target value没有出现在要查找的数组之中，然后要把这个值插入到数组中，插入的位置是最后跳出循环的low的值，可以用如下的逻辑来大致推理一下：

如果要找的数字是4, 数组中只有3和5,而没有4,最后low和high两个指针要退出循环之前要么同时指向3, 要么指向5, 如果是指向3, 那么此时mid = low = high, a[mid]会等于3 < 4, 下一次循环low指针会加1，也就是4要插入的位置。如果退出循环之前low和high同时指向5, 那么此时mid = low = high, a[mid]会等于5 > 4, 下一次循环high指针会减1, low指针位置不变，low指针还是4要插入的位置。

变形4加class设计拓展(结合HashMap)

  1. Time Based Key-Value Store

代码如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Data{
    String value;
    int timestamp;
    public Data(String value, int timestamp) {
        this.value = value;
        this.timestamp = timestamp;
    }
}
class TimeMap {
    
    Map<String, List<Data>> map;
    /** Initialize your data structure here. */
    public TimeMap() {
       map = new HashMap<String, List<Data>>();
    }
    
    public void set(String key, String value, int timestamp) {
        if(!map.containsKey(key)) map.put(key, new ArrayList<Data>());
        map.get(key).add(new Data(value, timestamp));
    }
    
    public String get(String key, int timestamp) {
        return binarySearch(map.get(key), timestamp);
    }
    
    public String binarySearch(List<Data> list, int timestamp) {
        int low = 0;
        int high = list.size()-1;
        while(low <= high) {
            int mid = low + ((high - low) >> 1);
            if(list.get(mid).timestamp <= timestamp){
                if(mid == list.size()-1 || list.get(mid+1).timestamp > timestamp){
                    return list.get(mid).value;
                }else{
                    low = mid + 1;
                }
            }else{
                high = low - 1;
            }
        }
        return "";
    }
}

针对rotated sorted array的二分查找(比较灵活，也容易出错)

  1. Search in Rotated Sorted Array
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 {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;
        while(low <= high) {
            int mid = low + ((high - low) >> 1);
            if(nums[mid] == target) return mid;
			
			if(nums[low] <= nums[mid]) { 
                if(nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }
            } else {
                if(nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }                                           
        }
        return -1;
    }
}

33的变形题，考虑到重复元素的出现

  1. Search in Rotated Sorted Array II

代码如下：

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
28
29
30
31
32
class Solution {
    public boolean search(int[] nums, int target) {
        // In worst case, the time complexity of this algorithm is O(n),
        int low = 0;
        int high = nums.length - 1;
        while(low <= high) {
            int mid = low +((high - low) >> 1);
            if(nums[mid] == target) return true;
            
            if(nums[low] < nums[mid]) {
                if(target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }
            }else if(nums[low] > nums[mid]) {
                if(nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else {
                //dealing with duplicates, we know nums[mid] != target, so nums[start] != target
                //based on current information, we can only move left pointer to skip one cell
                //thus in the worest case, we would have target: 2, and array like 11111111, then
                //the running time would be O(n)
                low ++;
            }
        }
        return false;
    }
}

主要注意如何处理duplicate elements那一块。而且要注意的是在最坏的情况下，即如果数组nums中的所有元素都相同的时候，算法的时间复杂度退化到O(n)。

33的变形题，要找rotated sorted array中最小的数，数组中没有重复元素的出现

  1. Find Minimum in Rotated Sorted Array

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high) {
            if(nums[low] < nums[high]) return nums[low]; 
            //上面这一行不可少，少了的话，下面nums[mid] == nums[low]时，可能会出错，而且有了这一行的检查在low到high之间的数据已经有序时，就可以返回最小值而不需要继续循环。

            int mid = low + ((high - low) >> 1);
            if(nums[mid] >= nums[low]) {
                low = mid + 1;
            }else{
                high = mid;
            }
        }
        return nums[low];
    }
}

注意这题，之前所有题目循环退出条件都是while(low <= high), 这一题是while(low < high)。如果写的是while(low <= high), 那么最后return的是nums[low-1]。有点绕，还不如上面代码的写法。

这道题再变形一下，可以找到maximum in rotated sorted array. 代码应该如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high) {
            if(nums[low] < nums[high]) return nums[high]; 

            int mid = low + ((high - low) >> 1);
            if(nums[mid] >= nums[low]) {
                low = mid;
            }else{
                high = mid-1;
            }
        }
        return nums[low];
    }
}

153的变形题，要找rotated sorted array中最小的数，数组中有重复元素

  1. Find Minimum in Rotated Sorted Array II

我第一次的做法，状态AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high) {
            int mid = low +((high - low) >> 1);
            if(nums[mid] < nums[high]) {
                high = mid;
            }else if(nums[mid] > nums[high]) {
                low = mid + 1;
            }else {
                high--;
            }
        }
        return nums[low];
    }
}

这个做法是在看153的题目的解答看到答案区别人给出的一个答案来的灵感。

这里把153题某网友的解答贴出来（原代码是C++，这里翻译成了java）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < nums[high])
                high = mid;
            else low = mid + 1;
        }

        return nums[low]; 
    }
}

这个写法和上面那个153的写法的区别在于到底是判断nums[mid]和nums[low]还是nums[high]的关系，前一种写法中的 if(nums[low] < nums[high]) return nums[high]; 这一行是必不可少的，但这个写法中没有这一个判断也可以的。(加上也可以，其实有这个判断我个人觉得是更好理解和记忆的。)

下面给出判断154的另一种解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high) {
            if(nums[low] < nums[high]) return nums[low]; 
            int mid = low + ((high - low) >> 1);
            if(nums[mid] > nums[low]) {
                low = mid + 1;
            }else if(nums[mid] < nums[low]){
                high = mid;
            }else{
                //if(mid == low) return Math.min(nums[mid], nums[high]);
                low++;
            }
        }
        return nums[low];
    }
}