经典算法 binary search 二分查找怎么实现?

二分查找很经典,当年看哈佛CS50是这么讲解的:怎么在字典里找某个单词?我们知道字典是按字母顺序排好序的。比如目标单词是cat,翻开字典中间,现在是g开头的词,那么我们知道cat肯定不在后半部分,那么可以把字典撕开,扔了后半部分。然后重复以上过程,中间翻开,这回是b开头的,就可以把前半部分仍了。如此下去,每次都把要搜索的空间减少一半,这样只用O(lgN)时间就能找到目标。不然的话一页页找的话就需要O(N)。虽然算法不复杂,但是要写对还是不容易的,以下经典实现最好背下来,内化到自己的知识库,就不用担心用到的时候边界条件不对。不然很容易进入死循环不返回,亲身经历。

代码如下:

Java

import java.util.Arrays;
import java.util.List;

public class Binarysearch {
    public static boolean binarySearch(int target, List<Integer> sortedlist) {
        if (sortedlist == null || sortedlist.isEmpty()) {
            return false;
        }
        int lower = 0;
        int upper = sortedlist.size()-1;
        while (lower <= upper) {
            int m = lower + (upper - lower) / 2;
            if (target == sortedlist.get(m)) {
                return true;
            } else if (target < sortedlist.get(m)) {
                upper = m - 1;
            } else {
                lower = m + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<Integer> sortedList = Arrays.asList(1, 3, 3, 7, 20, 48, 64, 72, 1024);
        int [] targets = {20, 32, 55, 72, 100};
        for (int target : targets) {
            System.out.println(String.format("%d in list? %b", target, binarySearch(target, sortedList)));
        }
    }
}

主要以下要点

  • while里面条件要是 lower <= upper
  • update lower bound 要是 m + 1
  • update upper bound 要是 m - 1
  • 计算中指用 m = lower + (upper - lower) / 2,而不是 (upper + lower) / 2,这样可以去除整数相加overflow问题。当然如果类型是bigint之类就无所谓了。

Leave a Comment

Your email address will not be published.