In C++Write a program that creates a 1000 element array with the data values of
ID: 674223 • Letter: I
Question
In C++Write a program that creates a 1000 element array with the data values of 10, 20, 30,... 10,000 in the elements. using binary search algorithm, search the array three times. Each time output how many comparisons were made by the search. The three searches should be for the values 30, 700, and 777(which should not be found).
Here is a binary search already in this file:
template <class elemType>
void mergeLists(elemType list[], elemType tempList[],
int first, int last, int m)
{
int i = first;
int j = m + 1;
int k = first;
while (i <= m && j <= last)
{
if (list[i] < list[j])
{
tempList[k] = list[i];
i = i + 1;
}
else
{
tempList[k] = list[j];
j = j + 1;
}
k = k + 1;
}
if (i <= m)
while (i <= m)
{
tempList[k] = list[i];
k = k + 1;
i = i + 1;
}
else
while (j <= last)
{
tempList[k] = list[j];
k = k + 1;
j = j + 1;
}
}
template <class elemType>
void recMergeSort(elemType list[], int first, int last)
{
elemType *tempList;
int m;
int i;
tempList = new elemType[last + 1];
if (first < last)
{
m = (first + last) / 2;
recMergeSort(list, first, m); //Merge sort list[first...m]
recMergeSort(list, m + 1, last); //Merge sort list[m+1...t]
mergeLists(list, tempList, first, last, m); //Merge list[first...m]
//and list[m+1...last];
//tempList[s...t] contains merged lists
for (i = first; i <= last; i++) //Copy tempList[first...last]
//into list[first...last]
list[i] = tempList[i];
}
}
template <class elemType>
void mergeSort(elemType list[], int length)
{
recMergeSort(list, 0, length - 1);
}
//********************
template <class elemType>
int seqSearch(const elemType list[], int length, const elemType& item)
{
int loc;
bool found = false;
loc = 0;
while (loc < length && !found)
if (list[loc] == item)
found = true;
else
loc++;
if (found)
return loc;
else
return -1;
} //end seqSearch
template <class elemType>
int binarySearch(const elemType list[], int length,
const elemType& item)
{
int first = 0;
int last = length - 1;
int mid;
bool found = false;
while (first <= last && !found)
{
mid = (first + last) / 2;
if (list[mid] == item)
found = true;
else if (list[mid] > item)
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
else
return -1;
} //end binarySearch
template <class elemType>
void bubbleSort(elemType list[], int length)
{
for (int iteration = 1; iteration < length; iteration++)
{
for (int index = 0; index < length - iteration;
index++)
{
if (list[index] > list[index + 1])
{
elemType temp = list[index];
list[index] = list[index + 1];
list[index + 1] = temp;
}
}
}
} //end bubbleSort
template <class elemType>
void selectionSort(elemType list[], int length)
{
int loc, minIndex;
for (loc = 0; loc < length; loc++)
{
minIndex = minLocation(list, loc, length - 1);
swap(list, loc, minIndex);
}
} //end selectionSort
template <class elemType>
void swap(elemType list[], int first, int second)
{
elemType temp;
temp = list[first];
list[first] = list[second];
list[second] = temp;
} //end swap
template <class elemType>
int minLocation(elemType list[], int first, int last)
{
int loc, minIndex;
minIndex = first;
for (loc = first + 1; loc <= last; loc++)
if (list[loc] < list[minIndex])
minIndex = loc;
return minIndex;
} //end minLocation
template <class elemType>
void insertionSort(elemType list[], int length)
{
for (int firstOutOfOrder = 1; firstOutOfOrder < length;
firstOutOfOrder++)
if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])
{
elemType temp = list[firstOutOfOrder];
int location = firstOutOfOrder;
do
{
list[location] = list[location - 1];
location--;
} while(location > 0 && list[location - 1] > temp);
list[location] = temp;
}
} //end insertionSort
template <class elemType>
void quickSort(elemType list[], int length)
{
recQuickSort(list, 0, length - 1);
} //end quickSort
template <class elemType>
void recQuickSort(elemType list[], int first, int last)
{
int pivotLocation;
if (first < last)
{
pivotLocation = partition(list, first, last);
recQuickSort(list, first, pivotLocation - 1);
recQuickSort(list, pivotLocation + 1, last);
}
} //end recQuickSort
template <class elemType>
int partition(elemType list[], int first, int last)
{
elemType pivot;
int index, smallIndex;
swap(list, first, (first + last) / 2);
pivot = list[first];
smallIndex = first;
for (index = first + 1; index <= last; index++)
if (list[index] < pivot)
{
smallIndex++;
swap(list, smallIndex, index);
}
swap(list, first, smallIndex);
return smallIndex;
} //end partition
template <class elemType>
void heapSort(elemType list[], int length)
{
buildHeap(list, length);
for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0;
lastOutOfOrder--)
{
elemType temp = list[lastOutOfOrder];
list[lastOutOfOrder] = list[0];
list[0] = temp;
heapify(list, 0, lastOutOfOrder - 1);
}//end for
}//end heapSort
template <class elemType>
void heapify(elemType list[], int low, int high)
{
int largeIndex;
elemType temp = list[low]; //copy the root node of
//the subtree
largeIndex = 2 * low + 1; //index of the left child
while (largeIndex <= high)
{
if (largeIndex < high)
if (list[largeIndex] < list[largeIndex + 1])
largeIndex = largeIndex + 1; //index of the
//largest child
if (temp > list[largeIndex]) //subtree
//is already in a heap
break;
else
{
list[low] = list[largeIndex]; //move the larger
//child to the root
low = largeIndex; //go to the subtree to
//restore the heap
largeIndex = 2 * low + 1;
}
}//end while
list[low] = temp; //insert temp into the tree,
//that is, list
}//end heapify
template <class elemType>
void buildHeap(elemType list[], int length)
{
for (int index = length / 2 - 1; index >= 0; index--)
heapify(list, index, length - 1);
}
Explanation / Answer
import java.util.Arrays; public class ArrayDemo { public static void main(String[] args) { // initializing unsorted int array int intArr[] = {30,20,5,12,55}; // sorting array Arrays.sort(intArr); // let us print all the elements available in list System.out.println("The sorted int array is:"); for (int number : intArr) { System.out.println("Number = " + number); } // entering the value to be searched int searchVal = 12; int retVal = Arrays.binarySearch(intArr,searchVal); System.out.println("The index of element 12 is : " + retVal); } }