diff options
author | Santo Cariotti <dcariotti24@gmail.com> | 2020-10-18 18:56:43 +0200 |
---|---|---|
committer | Santo Cariotti <dcariotti24@gmail.com> | 2020-10-20 09:08:52 +0200 |
commit | f279107065146a4940f5e73602a1c3c09e58b31d (patch) | |
tree | fd892749637a8b6c5c31ccb80bba04ade76ab87a /1_anno/Programmazione_2/algorithms/binarysearch.cc | |
parent | 4e063e32250312c38d5646840719b62429362b21 (diff) |
chore: name of first year folder
Diffstat (limited to '1_anno/Programmazione_2/algorithms/binarysearch.cc')
-rw-r--r-- | 1_anno/Programmazione_2/algorithms/binarysearch.cc | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/1_anno/Programmazione_2/algorithms/binarysearch.cc b/1_anno/Programmazione_2/algorithms/binarysearch.cc new file mode 100644 index 0000000..c9b4cd7 --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/binarysearch.cc @@ -0,0 +1,33 @@ +#include<iostream> + +using namespace std; + +bool bs(int a[], int i, int j, int x) { + if(j<i) return false; + int mid = i+(j-i)/2; + if(a[mid] == x) + return true; + if(a[mid] > 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 << ' '<<bs(a, 0, 9, i) << ' ' << bs2(a, 0, 9, i) << endl; + return 0; +} + |