From 7468f361189f9a32fb7d02e033d7174a3c1ef182 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sun, 19 Jul 2020 22:58:15 +0200 Subject: chore: binary search --- I_anno/Programmazione_2/algorithms/binarysearch.cc | 33 ++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 I_anno/Programmazione_2/algorithms/binarysearch.cc diff --git a/I_anno/Programmazione_2/algorithms/binarysearch.cc b/I_anno/Programmazione_2/algorithms/binarysearch.cc new file mode 100644 index 0000000..c9b4cd7 --- /dev/null +++ b/I_anno/Programmazione_2/algorithms/binarysearch.cc @@ -0,0 +1,33 @@ +#include + +using namespace std; + +bool bs(int a[], int i, int j, int x) { + if(j x) + return bs(a, i, mid-1, x); + return bs(a, mid+1, j, x); +} + +bool bs2(int a[], int i, int j, int x) { + while(i <= j) { + int mid = i+(j-i)/2; + if(a[mid] == x) return true; + if(a[mid] < x) + i = mid+1; + else + j = mid-1; + } + return false; +} + +int main() { + int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + for(int i = 0; i < 12; ++i) + cout << i << ' '<