* Complete function binarySearch() in main in order to perform a recursive binar
ID: 3737938 • Letter: #
Question
* Complete function binarySearch() in main in order to perform a
recursive binary search.
PLEASE ONLY PLACE CODE WHERE IT SAYS CODE HERE, DO NOT CHANGE ANY OTHER CODE
Main:
#include "intSortedArrayList.h"
int binarySearch(intSortedArrayList *arr, int l, int r, int x){
if(r < l){
/* CODE HERE */
}
int mid = (l + r) / 2;
int v = arr->getValue(mid);
if(x == v){
/* CODE HERE */
}
else if(x < v){
/* CODE HERE */
}
/* CODE HERE */
}
int main(){
int found = -1;
cout << "Creating a list of 20 integers" << endl << endl;
intSortedArrayList ar(20); // allocate 20 integers
srand(time(NULL)); // initialize random seed:
cout << "Inserting 10 elements" << endl;
for(int count = 1; count <= 10; ++count){
ar.insert(count*10);
}
cout << "Elements in the arrayList: ";
ar.print();
cout<< endl<< endl;
cout << "Searching element 50 " << endl;
found = binarySearch(&ar, 0, ar.listSize(), 50);
if(found != -1){
cout << "Found at index: " << found << " (value="
<< ar.getValue(found) << ")" << endl << endl;
}
else{
cout << "Not found" << endl << endl;
}
cout << "Inserting another 10 random elements" << endl;
for(int count = 1; count <= 10; ++count){
ar.insert(rand()%100);
}
cout << "Elements in the arrayList: " ;
ar.print();
cout<< endl<< endl;
cout << "Searching element 50 " << endl;
found = binarySearch(&ar, 0, ar.listSize(), 50);
if(found != -1){
cout << "Found at index: " << found << " (value="
<< ar.getValue(found) << ")" << endl << endl;
}
else{
cout << "Not found" << endl << endl;
}
cout << "Searching element 1050 " << endl;
found = binarySearch(&ar, 0, ar.listSize(), 1050);
if(found != -1){
cout << "Found at index: " << found << " (value="
<< ar.getValue(found) << ")" << endl << endl;
}
else{
cout << "Not found" << endl << endl;
}
return 0;
}
Header file:
#include <cstdlib>
#include <iostream>
#include <ctime>
using namespace std;
class intSortedArrayList {
protected:
int *list;
int maxSize;
int length;
public:
intSortedArrayList(int size) { // constructor
list = new int[size];
maxSize = size;
length = 0;
}
intSortedArrayList(){ // default constructor
list = new int[100];
maxSize = 100;
length = 0;
}
~intSortedArrayList() { // destructor
delete[] list;
}
void setValue(int index, int value) {
list[index] = value;
}
int getValue(int index) {
return list[index];
}
int listSize(){
return length;
}
int maxListSize(){
return maxSize;
}
void print(){
for(int i=0;i<length;i++){
cout << list[i] << " ";
}
}
bool isEmpty(){
return (length == 0);
}
bool isFull(){
return (length == maxSize);
}
void insert(int insertItem){
if(isEmpty()){
list[length++] = insertItem;
}
else if(isFull()){
cout << "Cannot insert in a full list." << endl;
}
else{
int i = 0;
while(list[i]<insertItem && i<length){
i++;
}
if(i==length) {
list[i] = insertItem;
length++;
}
else{
for(int j=length;j>i;j--){
list[j] = list[j-1];
}
list[i] = insertItem;
length++;
}
}
}
}; // end of class
Explanation / Answer
#include "intSortedArrayList.h"
int binarySearch(intSortedArrayList *arr, int l, int r, int x){
if(r < l){
/* CODE HERE */
return -1;
}
int mid = (l + r) / 2;
int v = arr->getValue(mid);
if(x == v){
/* CODE HERE */
return mid;
}
else if(x < v){
/* CODE HERE */
return binarySearch(arr, l, mid-1, x);
}
/* CODE HERE */
return binarySearch(arr, mid+1, r, x);
}
int main(){
int found = -1;
cout << "Creating a list of 20 integers" << endl << endl;
intSortedArrayList ar(20); // allocate 20 integers
srand(time(NULL)); // initialize random seed:
cout << "Inserting 10 elements" << endl;
for(int count = 1; count <= 10; ++count){
ar.insert(count*10);
}
cout << "Elements in the arrayList: ";
ar.print();
cout<< endl<< endl;
cout << "Searching element 50 " << endl;
found = binarySearch(&ar, 0, ar.listSize(), 50);
if(found != -1){
cout << "Found at index: " << found << " (value="
<< ar.getValue(found) << ")" << endl << endl;
}
else{
cout << "Not found" << endl << endl;
}
cout << "Inserting another 10 random elements" << endl;
for(int count = 1; count <= 10; ++count){
ar.insert(rand()%100);
}
cout << "Elements in the arrayList: " ;
ar.print();
cout<< endl<< endl;
cout << "Searching element 50 " << endl;
found = binarySearch(&ar, 0, ar.listSize(), 50);
if(found != -1){
cout << "Found at index: " << found << " (value="
<< ar.getValue(found) << ")" << endl << endl;
}
else{
cout << "Not found" << endl << endl;
}
cout << "Searching element 1050 " << endl;
found = binarySearch(&ar, 0, ar.listSize(), 1050);
if(found != -1){
cout << "Found at index: " << found << " (value="
<< ar.getValue(found) << ")" << endl << endl;
}
else{
cout << "Not found" << endl << endl;
}
return 0;
}
//Header file:
#include <cstdlib>
#include <iostream>
#include <ctime>
using namespace std;
class intSortedArrayList {
protected:
int *list;
int maxSize;
int length;
public:
intSortedArrayList(int size) { // constructor
list = new int[size];
maxSize = size;
length = 0;
}
intSortedArrayList(){ // default constructor
list = new int[100];
maxSize = 100;
length = 0;
}
~intSortedArrayList() { // destructor
delete[] list;
}
void setValue(int index, int value) {
list[index] = value;
}
int getValue(int index) {
return list[index];
}
int listSize(){
return length;
}
int maxListSize(){
return maxSize;
}
void print(){
for(int i=0;i<length;i++){
cout << list[i] << " ";
}
}
bool isEmpty(){
return (length == 0);
}
bool isFull(){
return (length == maxSize);
}
void insert(int insertItem){
if(isEmpty()){
list[length++] = insertItem;
}
else if(isFull()){
cout << "Cannot insert in a full list." << endl;
}
else{
int i = 0;
while(list[i]<insertItem && i<length){
i++;
}
if(i==length) {
list[i] = insertItem;
length++;
}
else{
for(int j=length;j>i;j--){
list[j] = list[j-1];
}
list[i] = insertItem;
length++;
}
}
}
}; // end of class
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.