本文介绍了如何对已经排序的 vector 进行二分法查找。
首先，我们先看一下存储数据的类，我们假设所有数据的 id 是唯一的：
DataItem.h
#pragma once
#include<string>namespace zc {class DataItem{public:int m_id;std::string m_name;std::string m_data;DataItem(int id, std::string name, std::string data);~DataItem();};
}
DataItem.cpp
#include "DataItem.h"using namespace zc;DataItem::DataItem(int id, std::string name, std::string data):m_id(id), m_name(name), m_data(data)
{
}DataItem::~DataItem(){}
存储在 vector 中的元素，都是 DataItem 类实例化的对象。这些对象在 vector 中按照 id 从低到高排列。如果我们要提高按照 id 查找的效率，可以使用二分法查找（也叫折半查找）。
算法实现的思路如下：
-
假设 vector 的长度是 N，循环次数是以 2 为底 N 的对数。程序先强制转换为 int，然后给整型变量 times 赋值循环次数。
-
循环开始前，设置
begin是 0，代表第一个元素的下标。end是最后一个元素的下标。 -
开启循环，循环次数就是 times。只要循环次数达到 times 就停止循环。
-
在循环中，计算中间元素的下标，取出中间元素。
-
如果输入 id 小于中间元素的下标，给 end 赋值中间元素坐标减一。反之，给 begin 赋值中间元素坐标。通过循环不断缩小 begin 和 end 之间的范围。因为 vector 的长度不可能总是等于 2 整数次方，再加上循环次数强制转换为整型，所以 begin 和 end之间要么相等，要么 end 比 begin 大一。
-
上一个循环结束后，开启从 begin 到 end 的循环，如果能找到 id 相同的元素并返回下标，如果没找到就返回 -1.
下面是具体实现的 C++ 代码：
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <cmath>
#include "DataItem.h"
#include <chrono>// 向 vector 中添加元素
void addItem(std::vector<zc::DataItem> &vector) {for (int i = 1; i < 100000; i++) {std::string no = std::to_string(i);vector.push_back(zc::DataItem(i, "name_" + no, "data_" + no));}}// 使用二分法查找算法，从 vector 中查找指定 id 的对象的序号.
// vector: 已经排好序的列表
// id: 要查找的指定ID
int findIndexByBinary(const std::vector<zc::DataItem> vector, const int id) {int result = -1;int size = vector.size();if (0 == size) {return -1;}// 只有一条数据就直接判断然后返回。if (1 == size) {if (vector[0].m_id == id) {result = 0;}return result;}int begin = 0;int end = size - 1;// 计算以2为底的对数，进而确定要循环多少次找到目标数据double log2Result = log2((double)size);int times = (int)log2Result;// 不断缩小begin和end的范围。有可能 begin 等于 end，也有可能 end 比 begin 大一。for (int i = 0; i < times; i++) {int tmpLen = end - begin + 1;int halfIndex = begin + (tmpLen / 2);zc::DataItem item = vector[halfIndex];if (id < item.m_id) {end = halfIndex - 1;}else {begin = halfIndex;}}//printf("begin=%d, end=%d\n", begin, end);for (int i = begin; i <= end; i++) {zc::DataItem tmp = vector[i];if (id == tmp.m_id) {result = i;break;}}return result;
}// 遍历vector,从 vector 中查找指定 id 的对象的序号.
int findIndex(const std::vector<zc::DataItem> vector, const int id) {int result = -1;int size = vector.size();if (0 == size) {return -1;}for (int i = 0; i < size; i++) {zc::DataItem tmp = vector[i];if (id == tmp.m_id) {result = i;break;}}return result;
}long long nowMS()
{long long result =std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();return result;
}int main(int argc, char** argv) {system("color 02");printf("hello argc=%d argv[0]=%s\n\n", argc, argv[0]);long long t1 = 0, t2 = 0;int index = -1;std::vector<zc::DataItem> vector;addItem(vector);t1 = nowMS();const int id = 95001;index = findIndexByBinary(vector, id);t2 = nowMS();if (index < 0) {return -1;}zc::DataItem item = vector[index];printf("index=%d, id=%d, name=%s, data=%s, time=%lld\n", index, item.m_id, item.m_name.c_str(), item.m_data.c_str(), (t2 - t1));t1 = nowMS();index = findIndex(vector, id);t2 = nowMS();zc::DataItem item2 = vector[index];printf("index=%d, id=%d, name=%s, data=%s, time=%lld\n", index, item2.m_id, item2.m_name.c_str(), item2.m_data.c_str(), (t2 - t1));printf("\n\n");
}
 附源码)
--DatePicker)
