1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
void bubblesort(int ptableau[], int n)
{
int i, j, temp;
for (i = 0; i < (n - 1); ++i) {
for (j = i + 1; j < n; ++j) {
if (ptableau[j] < ptableau[i]) {
temp = ptableau[i];
ptableau[i] = ptableau[j];
ptableau[j] = temp;
}
}
}
}
int binarySearch(int X[],int key,int sup,int inf){
int m;
while(sup >= inf){
m=(sup + inf)/2;
if(key < X[m])
sup = m - 1;
else
if(key > X[m])
inf = m + 1;
else
return m;
}
return -1;
}
int main(){
int const SIZE = 50000;
int xInt[SIZE];
int key = -5;
srand(time(NULL));
for(int i = 0;i < SIZE;i++){
xInt[i] = rand()%1000;
}
bubblesort(xInt, SIZE);
int found = binarySearch(xInt,key,SIZE,0);
if( found == -1)
cout<<"La valeur n'est pas trouvée !";
else
cout<<"La clé se trouve dans la case numéro "<<found + 1;
return 0;
} |
