I am working on a project for school that tests Binary Search vs. Linear Search. My LinearSearch method seems to work fine when the array is in either increasing order or reversed. However, the BinarySearch only works when the array is in increasing order, but fails to work when the array is reversed. I am not sure what is causing this and would appreciate any suggestions/solutions.
Here is my code
/*
* SearchTest.cpp
*
* Created on: Oct 16, 2022
* Author: JH
*/
#include <iostream>
#include <time.h>
using namespace std;
//BinarySearch method
int BinarySearch(int numbers[], int numbersSize, int key) {
int mid;
int low;
int high;
low = 0;
high = numbersSize - 1;
while (high >= low) {
mid = (high + low) / 2;
if (numbers[mid] < key) {
low = mid + 1;
}
else if (numbers[mid] > key) {
high = mid - 1;
}
else {
return mid;
}
}
return -1; // not found
}
//LinearSearch method
int LinearSearch(int* array, int arraySize, int key) {
for (int i = 0; i < arraySize; i++) {
if (array[i] == key) {
return i;
}
}
return -1; // not found
}
//method to reverse array elements
void reverseArray(int arr[], int start, int end)
{
while (start < end)
{
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
int main() {
//declare array
int reverseArr[1000];
int size = sizeof(reverseArr)/sizeof(reverseArr[0]);
//initialize array
for (int i = 0; i < size; i++) {
reverseArr[i] = i;
}
//reverse array
reverseArray(reverseArr, 0, size-1);
//print array
for (int i = 0; i < size; i++) {
cout << reverseArr[i] << " ";
}
cout << endl;
cout << endl;
//generate random number
srand(time(NULL));
int randomNum = rand() % 1000;
//print statements
cout << "[Linear vs. Binary Search]" << endl;
cout << "The target value is " << reverseArr[randomNum] << endl;
cout << endl;
//call BinarySearch method for array
cout << "Binary Search Test: " << endl;
int key1 = reverseArr[randomNum];
int keyIndex1 = BinarySearch(reverseArr, size, key1);
if (keyIndex1 == -1) {
cout << key1 << " was not found." << endl;
}
else {
cout << "Found " << key1 << " at index " << keyIndex1 << "." << endl;
}
cout << endl;
//call LinearSearch method for array
cout << "Linear Search Test: " << endl;
int key2 = reverseArr[randomNum];
int keyIndex2 = LinearSearch(reverseArr, size, key2);
if (keyIndex2 == -1) {
cout << key2 << " was not found." << endl;
}
else {
cout << "Found " << key2 << " at index ";
cout << keyIndex2 << "." << endl;
}
}