Algorithms : complete 01-algorithmic_toolbox 03-divide_and_conquer

1 files changed, 12 insertions, 5 deletions

diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
index c93e2cf..40f8f01 100644
--- a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
@@ -4,9 +4,16 @@
 
 using std::vector;
 
-int binary_search(const vector<int> &a, int x) {
-  int left = 0, right = (int)a.size(); 
-  //write your code here
+int binary_search(const vector<int> &a, int x)
+{
+  int left = 0, right = (int) a.size();
+  while (left <= right) {
+      int mid = (left + right) / 2;
+      if (a[mid] == x) return mid;
+      if (a[mid] < x) left = (mid + 1);
+      else right = (mid - 1);
+  }
+  return -1;
 }
 
 int linear_search(const vector<int> &a, int x) {
@@ -30,7 +37,7 @@ int main() {
     std::cin >> b[i];
   }
   for (int i = 0; i < m; ++i) {
-    //replace with the call to binary_search when implemented
-    std::cout << linear_search(a, b[i]) << ' ';
+    std::cout << binary_search(a, b[i]) << ' ';
   }
+  std::cout << '\n';
 }