lower_bound and upper_bound algo in C++ added.

liuyubobobo · liuyubobobo · commit be14a2a68a82 · 2017-11-16T23:28:17.000-08:00
diff --git a/05-Binary-Search-Tree/Course Code (C++)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/CMakeLists.txt b/05-Binary-Search-Tree/Course Code (C++)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(Optional_03_Lower_Bound_and_Upper_Bound_in_Binary_Search)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main.cpp)
+add_executable(Optional_03_Lower_Bound_and_Upper_Bound_in_Binary_Search ${SOURCE_FILES})
diff --git a/05-Binary-Search-Tree/Course Code (C++)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/main.cpp b/05-Binary-Search-Tree/Course Code (C++)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/main.cpp
@@ -0,0 +1,49 @@
+#include <iostream>
+#include <cassert>
+
+using namespace std;
+
+// 二分查找法, 实现lower_bound
+// 即在一个有序数组arr中, 寻找大于等于target的元素的第一个索引
+// 如果存在, 则返回相应的索引index
+// 否则, 返回arr的元素个数 n
+template<typename T>
+int lower_bound(T arr[], int n, T target){
+
+    assert(n >= 0);
+
+    int l = 0, r = n;
+    while(l != r){
+        int mid = l + (r - l) / 2;
+        if(arr[mid] < target)
+            l = mid + 1;
+        else    // nums[mid] >= target
+            r = mid;
+    }
+    return l;
+}
+
+// 二分查找法, 实现upper_bound
+// 即在一个有序数组arr中, 寻找大于target的元素的第一个索引
+// 如果存在, 则返回相应的索引index
+// 否则, 返回arr的元素个数 n
+template<typename T>
+int upper_bound(T arr[], int n, T target){
+
+    assert(n >= 0);
+
+    int l = 0, r = n;
+    while(l != r){
+        int mid = l + (r - l) / 2;
+        if(arr[mid] <= target)
+            l = mid + 1;
+        else    // nums[mid] > target
+            r = mid;
+    }
+    return l;
+}
+
+int main() {
+    
+    return 0;
+}
diff --git a/README.md b/README.md
@@ -121,7 +121,7 @@
 | 本章课程最终代码 | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Chapter-05-Completed-Code) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Chapter-05-Completed-Code/src/bobo/algo) |
 | 补充1 二分查找法改变变量定义，论如何写出正确算法 | [玩转算法面试](http://coding.imooc.com/class/82.html) | [第三章1，2小节](http://coding.imooc.com/lesson/82.html#mid=2656) |
 | 补充2 二分搜索法的floor和ceil | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil-in-Binary-Search) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-02-Floor-and-Ceil-in-Binary-Search/src/bobo/algo/) |
-| 补充3 二分搜索法的lower bound和upper bound | [整理中] | [敬请期待] |
+| 补充3 二分搜索法的lower bound和upper bound | [C++源码](05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-03-Lower-Bound-and-Upper-Bound-in-Binary-Search/) | [Java源码][敬请期待] |
 | 补充4 二分搜索的总结 | [整理中] | [敬请期待] |
 | 补充5 二分搜索树中的floor和ceil | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-05-Floor-and-Ceil-in-BST/) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-05-Floor-and-Ceil-in-BST/src/bobo/algo/) |
 | 补充6 二分搜索树中的前驱和后继 | [C++源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-06-Predecessor-and-Successor-in-BST/) | [Java源码](https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-06-Predecessor-and-Successor-in-BST/src/bobo/algo/) |
