二分查找（图5-2）在预先排好序的集合上表现出了比顺序查找更好的性能。二分查找每次将有序集合折半直到找到待查找元素，或者发现待查找元素不在当前的集合中。
图 5-2 二分查找详解假设你有一本纽约电话簿，并且需要找到"David Mamet"的电话。如果你使用顺序查找的话，你也许需要花费下午的大部分时间来寻找他的电话号码，或者更坏的是，在知道他的号码是否已经列出之前，你不得不检查电话簿中的每一个条目。很明显的，这个方法没有利用电话簿上名字有序这个特性。所以，你可以翻到电话簿的中页看看"David Mamet"是否在那页上。如果"David Mamet"这个条目在那一页，那么就到此为止。如果不在，并且"Mamet"在字典序上比这一页上任何一个姓都要靠前，那么你需要在电话簿的前半部去寻找。否则的话，你就需要在电话簿的后半部寻找。这个过程是一种“分治”的策略，能够快速地定位想要找的目标。注意，如果你翻到某一页，这一页上"Mamet"应该出现但是没有出现，那么你知道不用再去查找任何一页，因为Mamet的电话不在这本电话簿上。
输入/输出
二分查找的输入是一个索引集合A。每一个元素A[i]有一个键值ki能够用来区分元素。这些键值是有序的，意思是，给定两个键值ki和kj，要么ki＜kj，要么ki=kj，或者ki＞kj。我们构造了一个数据结构来保存这些元素（或者这些元素的指针）和维护键值的有序。我们也必须能够将这个数据结构分成数个子集进行查找，这样我们就使用了“分治法”来解决这个问题。二分查找的输出是真或者假。