Question

An easier way to do the Binary Search part or a simplistic way for beginners. Not using such high code for the assignment in general also commenting on what each line does.

COMMENT ON the code below .what does each part do for the program? and a better and more simple and basic way to do binary search and get same results.

#include <iostream>
#include <fstream>
using namespace std;

void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
void bubbleSort(int numbers[], int n)
{
int i, j, count = 0;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (numbers[j] > numbers[j+1]){
swap(&numbers[j], &numbers[j+1]);
count++;
}
cout << "No of exchanges in bubble sort is " << count << endl;
}

void selectionSort(int numbers2[], int n)
{
int i, j, min_idx, count = 0;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
if (numbers2[j] < numbers2[min_idx])
min_idx = j;
swap(&numbers2[min_idx], &numbers2[i]);
count++;
}
cout << "No of exchanges in selection sort is " << count << endl;
}
void linearSearch(int numbers[]){
int count = 0;
for(int i = 0; i < 200; i++){
count++;
if(numbers[i] == 869)
break;
}
cout << "No of comparisons in linear search is " << count << endl;
}
int binarySearch(int numbers[], int l, int r, int x, int count)
{
if (r >= l)
{
count++;
int mid = l + (r - l)/2;
if (numbers[mid] == x)
return count;
if (numbers[mid] > x)
return binarySearch(numbers, l, mid-1, x, count);
return binarySearch(numbers, mid+1, r, x, count);
}
return -1;
}
int main()
{
fstream myfile("data.txt", std::ios_base::in);
int a, numbers[200], count = -1;
while (myfile >> a)
{
count++;
numbers[count] = a;
}
int numbers2[200];
for(int i = 0; i < 200; i++)
numbers2[i] = numbers[i];
bubbleSort(numbers, 200);
selectionSort(numbers2, 200);
linearSearch(numbers);
int res = binarySearch(numbers,0, 199, 869, 0);
cout << "No of comparisons in binary search is " << res << endl;
return 0;
}

the randomn.txt file contains these values :

42 468 335 501 170 725 479 359 963 465 706 146 282 828 962 492 996 943 828 437 392 605 903 154 293 383 422 717 719 896 448 727 772 539 870 913 668 300 36 895 704 812 323 334 674 665 142 712 254 869 548 645 663 758 38 860 724 742 530 779 317 36 191 843 289 107 41 943 265 649 447 806 891 730 371 351 7 102 394 549 630 624 85 955 757 841 967 377 932 309 945 440 627 324 538 539 119 83 930 542 834 116 640 659 705 931 978 307 674 387 22 746 925 73 271 830 778 574 98 513 987 291 162 637 356 768 656 575 32 53 351 151 942 725 967 431 108 192 8 338 458 288 754 384 946 910 210 759 222 589 423 947 507 31 414 169 901 592 763 656 411 360 625 538 549 484 596 42 603 351 292 837 375 21 597 22 349 200 669 485 282 735 54 1000 419 939 901 789 128 468 729 894 649 484 808 422 311 618 814 515

Answer 1

#include <iostream>

#include <fstream>

using namespace std;

//A utility function to swap two values of two variables

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

//A utility function to display array elements

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

}

//A utitlity function to sort array using bubble sort

void bubbleSort(int numbers[], int n)

{

int i, j, count = 0;

for (i = 0; i < n-1; i++)

// Last i elements are already in sorted order

for (j = 0; j < n-i-1; j++)

if (numbers[j] > numbers[j+1]){

swap(&numbers[j], &numbers[j+1]);

count++;

}

}

cout << "No of exchanges in bubble sort is " << count << endl;

}

//A utility function to sort array using selection sort

void selectionSort(int numbers2[], int n)

{

int i, j, min_idx, count = 0;

// One by one find smallest element form remaining unsorted array

// and keep it at its right position

for (i = 0; i < n-1; i++)

{

min_idx = i;

for (j = i+1; j < n; j++)

if (numbers2[j] < numbers2[min_idx])

min_idx = j;

// Swap the found minimum element with the first element

swap(&numbers2[min_idx], &numbers2[i]);

count++;

}

cout << "No of exchanges in selection sort is " << count << endl;

}

//A function to find an element in the array

void linearSearch(int numbers[],int searchValue)

{

int count = 0;

//A loop from 0 to 200 to find whether value to search is present in array or not

for(int i = 0; i < 200; i++)

{

count++;

if(numbers[i] == searchValue)

{

cout<<"Value found"<<endl;

break;

}

}

cout<<"Value not found"<<endl;

}

cout << "No of comparisons in linear search is " << count << endl;

}

int binarySearch(int numbers[], int l, int r, int x, int count)

{

if (r >= l)

{

count++;

// If the element is present at the middle

int mid = l + (r - l)/2;

if (numbers[mid] == x)

return count;

// If element is smaller than mid, then

// it can only be present in left subarray

if (numbers[mid] > x)

return binarySearch(numbers, l, mid-1, x, count);

// Else the element can only be present

// in right subarray

return binarySearch(numbers, mid+1, r, x, count);

}

//Value not present in the array

return -1;

}

int main()

{

//Opening a file in read mode

fstream myfile("data.txt", std::ios_base::in);

int a, numbers[200], count = -1;

while (myfile >> a)

{

count++;

numbers[count] = a;

}

int numbers2[200];

for(int i = 0; i < 200; i++)

numbers2[i] = numbers[i];

//Function to sort array using bubble sort

bubbleSort(numbers, 200);

//Function to sort array using selection sort

selectionSort(numbers2, 200);

//Function to search an element in array linearly

linearSearch(numbers);

//Function to search an element in array using binary search

int res = binarySearch(numbers,0, 199, 869, 0);

cout << "No of comparisons in binary search is " << res << endl;

return 0;

}

//Easier way to do binary search

int binarySearch(int arr[],int l,int r,int x)

{

while (l<=r)

{

int mid=l+(r-l)/2;

// Check if x is present at mid

if (arr[mid]==x)

return mid;

// If x greater, ignore left half

if (arr[mid]<x)

l=mid+1;

// If x is smaller, ignore right half

else

r=mid-1;

}

//Element is not present in the array

return -1;

}