Using Divide and Conquer Strategies design a function for Binary Search using C++/ Java/ Python/ Scala.

1:  /*  
2:    >> g++ binarysearch.cpp  
3:    >> ./a.out  
4:  */  
5:  #include"iostream"  
6:  #include"stdlib.h"  
7:  using namespace std;  
8:  class BinarySearch  
9:  {  
10:    public:  
11:      int search(int *arr, const int len, const int s)  
12:      {  
13:        int lower = 0;  
14:        int upper = len - 1;  
15:        int middle = (lower+upper)/2;  
16:        while (lower <= upper)  
17:        {  
18:          if (arr[middle] == s)  
19:            return middle;  
20:          else if (arr[middle] > s)  
21:            upper = middle-1;  
22:          else  
23:            lower = middle+1;  
24:          middle = (lower + upper)/2;  
25:        }  
26:        return -1;  
27:      }  
28:      void quicksort(int *arr, const int size)  
29:      {  
30:        if(size == 1 || size == 0)  
31:          return;  
32:        int pivot = arr[0];  
33:        int *arrl = new int[size];  
34:        int *arrh = new int[size];  
35:        int j=0, k=0;  
36:        for(int i=1; i<size; i++)  
37:        {  
38:          int element = arr[i];  
39:          if( element <= pivot )  
40:            arrl[j++] = element;  
41:          else  
42:            arrh[k++] = element;  
43:        }  
44:        quicksort(arrl, j);  
45:        int p=0;  
46:        for(int i=0; i<j; i++)  
47:          arr[p++] = arrl[i];  
48:        arr[p++] = pivot;  
49:        quicksort(arrh, k);  
50:        for(int i=0; i<k; i++)  
51:          arr[p++] = arrh[i];  
52:        delete(arrl); delete(arrh);  
53:      }  
54:  }b;  
55:  int main()  
56:  {  
57:    cout<<"\n\n^_^_^_^_^_^_^_^_^_^_^_^ Binary Search ^_^_^_^_^_^_^_^_^_^_^_^";  
58:    int len, s;  
59:    cout<<"\n\nEnter size of an array: ";  
60:    cin>>len;  
61:    int arr[len];  
62:    cout<<"\nEnter elements of sorted array: ";  
63:    for(int i=0; i<len; i++)  
64:      cin>>arr[i];  
65:    b.quicksort(arr, len);  
66:    cout<<"\nSorted array: [ ";  
67:    for(int i=0; i<len; i++)  
68:      cout<<arr[i]<<" ";  
69:    cout<<"]";  
70:    cout<<"\n\nEnter element to be searched: ";  
71:    cin>>s;  
72:    int result = b.search(arr, len, s);  
73:     if(result != -1)  
74:       cout<<"\n\n"<< s <<" successfully found in the array at index "<< result <<".\n\n";  
75:    else  
76:       cout<<"\n\nOops. :( Element "<< s <<" is not found in the given array.\n\n";  
77:     return 0;  
78:  }