BinarySearch not working for reversed array

36 Views Asked by At

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;
    }

}
0

There are 0 best solutions below