summaryrefslogtreecommitdiff
path: root/I_anno/Programmazione_2
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-07-19 22:58:15 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-07-19 22:58:15 +0200
commit7468f361189f9a32fb7d02e033d7174a3c1ef182 (patch)
treec0e3d35997b4dee3a30baca321df4289b90cbac2 /I_anno/Programmazione_2
parent3833c952f1dff3957bc423045df6d52c14a6db78 (diff)
chore: binary search
Diffstat (limited to 'I_anno/Programmazione_2')
-rw-r--r--I_anno/Programmazione_2/algorithms/binarysearch.cc33
1 files changed, 33 insertions, 0 deletions
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<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;
+}
+