《Discrete Mathematics and Its Applications》( Page 195) 学习笔记

point 1

离散地去想means（这些int是“一个个”的）:

To search for 19 in the list
1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 split: 1 2 3 5 6 7 8 10(mid)               12 13 15 16 18 19 20 22 .because 19 > 10(mid): 12 13 15 16 18 19 20 22.split: 12 13 15 16(mid)             18 19 20 22.because 19 > 16(mid): 18 19 20 22.split: 18 19(mid)         20 22.because 19 == 19(mid): break, return mid To search for 17 in the list
1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22  （now left->1, right->22）split: 1 2 3 5 6 7 8 10(mid)               12 13 15 16 18 19 20 22 .because 17 > 10(mid): 12 13 15 16 18 19 20 22. （now left->12, right->22）split: 12 13 15 16(mid)             18 19 20 22.because 17 > 16(mid): 18 19 20 22.  （now left->18, right->22）split: 18 19(mid)         20 22.because 17 < 19(mid):  18 19  （now left->18, right->19）split: 18(mid)     19    because 17 < 18(mid): 18 （now left->18, right->18, fall out of the loop）

mid = (left + right)/2 floor # 感觉是取中间(odd)或者取中间偏前一个位置(mean)的作为mid，所以向下取整啦list .end(), .begin()， 则中分sublist中元素个数不会多于 (.end() - .begin()) / 2 ceil # .end() - .begin()即list中元素个数

point 2，3，4，5

// iseq: ascending
size_t bi_search_first(const vector<int>& iseq, int target)
{if (!iseq.empty()) {size_t left = 0, right = iseq.size() - 1;size_t mid = 0;while (left != right) { // 2. left==right即查找范围只有一个int时fall out of the loop
// 不是iseq[mid] == target时fall out of loop
//（如果target not exist, 
// the loop will end up looping at one element infinitely 
// (when the left end point equals the right end point, 
// the middle computed is always still the left( or right) end point, 
// and continue to be not equal to the target, and the loop will never ends ) ）mid = (left + right) / 2;if (iseq[mid] == target) {return mid;}// if iseq[mid] != mid :if (iseq[mid] > target) { // 3. 如果上面没有那个iseq[mid]==target check的话，此处得有=，只有>不行// 如果此处只有>，则如果iseq[mid]==target时会重置left为mid+1，即查找范围绕过了mid，而mid是我们要找的 走right = mid的话范围包括了midright = mid;}else {left = mid + 1; // 4. left得置为mid+1，这样才保证出现left = right（考虑最后查找list只有两个int时，mid此时是等于left的，// 如果比较得出的是保留右侧的sublist且left是置为mid的话，那就会出现最后left和right一直保持不变永远相差1无限循环）// 另外这样分成的两个sublist没有overlap}}// 5. 查找范围只剩一个int时的收尾check（在fall out of loop前没有check，left和right刚算出来，发现equal就fall out了）if (iseq[left] == target) {return left;}return -1; // used to initialize an *unsigned* temp}
}

implementation by c++

// iseq: ascending
size_t bi_search_first(const vector<int>& iseq, int target)
{if (!iseq.empty()) {size_t left = 0, right = iseq.size() - 1;size_t mid = 0;while (left != right) { mid = (left + right) / 2;if (iseq[mid] == target) {return mid;}// if iseq[mid] != mid :if (iseq[mid] > target) { right = mid;}else {left = mid + 1; }}if (iseq[left] == target) {return left;}return -1; // indicate not found}
}