C++程式設計：原理與實踐（進階篇）16.8 排序和搜尋

<b>16.8　排序和搜尋</b>

<b></b>

我們經常希望自己的資料是有序的。為達到這個目的，我們可以使用一個能維護順序的資料結構，例如map或set，或進行排序。在stl中，最常見和有用的排序操作是sort()，我們已經使用過多次了。在預設情況下，sort()使用&lt;作為排序标準，但是我們也可以提供自己的标準：

作為一個基于使用者指定規則進行排序的例子，我們将介紹如何進行不考慮大小寫的字元串排序：

一旦一個序列已排序，我們不再需要用f?ind()從開始位置進行搜尋；我們可以利用這種序進行二分搜尋。二分搜尋的基本工作原理如下：

假設我們在查找值x，檢視中間元素：

如果元素的值等于x，我們已經找到它！

如果元素的值小于x，則值等于x的任何元素必然位于右邊，是以我們查找右半部分（在這半部分進行二分查找）。

如果元素的值大于x，則值等于x的任何元素必然位于左邊，是以我們查找左半部分（在這半部分進行二分查找）。

如果我們已經到達最後一個元素（向左或向右），也沒有找到x，那麼沒有等于值x的元素。

對于更長的序列，二分搜尋比f?ind()（線性搜尋）的速度更快。二分搜尋的标準庫算法是binary_search()和equal_range()。我們說的“更長”的含義是什麼呢？這要視具體情況而定，但即使序列中隻有10個元素，也足以展現出binary_search()相對于f?ind()的優勢。對于一個有1000個元素的序列，binary_search()可能要比f?ind()快200倍，因為其代價為o(log2(n))，參見16.6.4節。

binary_search算法有兩種變形：

這些算法要求和假設輸入序列是已排序的。如果未排序，“有趣的事情”如無限循環就可能會發生。binary_search()簡單地告訴我們一個值是否存在：

是以，如果我們隻關心一個值是否在序列中，binary_search()是理想的。如果我們還關心找到的元素，可以使用low_bound()、upper_bound()或equal_range()（參見附錄c.5.4和23.4節）。有些情況下我們關心找到的是哪個元素，原因通常是對象包含更多資訊而不僅僅是一個關鍵字，而很多元素可能具有相同的關鍵字，或者是我們希望找到符合搜尋标準的元素。