# quick sort and binary search

Dec 20th, 2016
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. using namespace std;
3.
4.
5. void swap (int &a, int &b) {
6. int c = 0;
7. c = a;
8. a = b;
9. b = c;
10. }
11. void qs (int *arr, int low, int high){
12. int a = high;
13. int i = low - 1;
14. if (low < high) {
15. for (int j = low; j < high; j++){
16. if (arr[a] > arr[j]) {
17. i++;
18. swap (arr[i], arr[j]);
19. }
20. }
21. swap(arr[a], arr[i+1]);
22. qs (*&arr, low, i);
23. qs (*&arr, i+2, high);
24. }
25. }
26. void bs (int arr[], int k, int low, int high){
27. int x = high/2;
28. if (low < high){
29. if (arr[x] < k){
30. bs(arr, k, x+1, high);
31. } else if (arr[x] > k) {
32. bs(arr, k, low, x-1);
33. } else if (arr[x] == k) {
34. cout << " Found " << k << " at " << x+1;
35. }
36. } else if (low == high) {
37. if (arr[high] == k){
38. cout << " Found " << k << " at " << high+1;
39. } else {
41. }
42. }
43. }
44. int main() {
45. int n, s;
46. cout << "How many integers you want to input : ";
47. cin >> n;
48. int array[n];
49. for (int x = 0; x < n; x++){
50. cin >> array[x];
51. }
52. qs(array, 0, n-1);
53. cout << "Ouput of sorted array : ";
54. for (int x = 0; x < n; x++){
55. cout << array[x] << " ";
56. }
57. cout << endl << "Which element do you want to search for? ";
58. cin >> s;
59. bs (array, s, 0, n-1);
60. return 0;
61. }