$12\mathrm{.}3($Binary Search$)$

Rewrite the binary search function in Listing $7\mathrm{.}6($copied below$),$ BinarySearch.cpp to use a generic type for array elements. Test the function with an array of int, double, and string values.

Listing $7\mathrm{.}6$ BinarySearch.cpp

#include

using namespace std;

int binarySearch$($const int list$[],$ int key, int listSize$)$;

int main$()$

$\{$

int list$[]=\{-3,1,2,4,9,23\}$;

cout $<<$ binarySearch$($list$,2,6)<<$ endl;

return $0$;

$\}$

int binarySearch$($const int list$[],$ int key, int listSize$)$

$\{$

int low $=0$;

int high $=$ listSize $-1$;

while $($high $>=$ low$)$

$\{$

int mid $=($low $+$ high$)/2$;

if $($key $<$ list$[$mid$])$

high $=$ mid $-1$;

else if $($key $==$ list$[$mid$])$

return mid;

else

low $=$ mid $+1$;

$\}$

return $-$low $-1$;

$\}$

You may test your code with the following arrays:

int intArray$[]=\{1,2,3,4,8,15,23,31,45,56,67,466,656,788,899\}$;

double doubleArray$[]=\{0\mathrm{.}1,2\mathrm{.}5,3\mathrm{.}6,4\mathrm{.}7,8\mathrm{.}8,15\mathrm{.}8,23\mathrm{.}4,31\mathrm{.}5,45\mathrm{.}6,56\mathrm{.}6,67\mathrm{.}5,466\mathrm{.}5,656\mathrm{.}7,788\mathrm{.}9,899\mathrm{.}9\}$;

string cities$[]=\{"$Atlanta$",$ "Augusta", "Burbank", "Glendale". "Macon", "Pasadena", "Savannah", "Sylmar"$\}$;