Big Jump in Number of Binary search checks?

[Arslan7041]

So I made the following program which shows the difference between linear and binary search, in terms of the number of checks each takes to find the search value in the array.

#include <iostream>

using namespace std;

// Prototype functions
void FillArray(int[], int);
int LinearSearch(int[], int, int);
int BinarySearch (int[], int, int);

int main()
{
    //sets array size;
    int ARRAY_SIZE;

    cout << "Enter in size of array: " << flush;
    cin >> ARRAY_SIZE;

    int arr[ARRAY_SIZE];

    int searchValue;

    cout << "Enter in a number between 0 and " << ARRAY_SIZE << " to search for: " << flush;
    
    cin >> searchValue;

    cout << "\n\n";

    // Function call to fill array
    FillArray(arr, ARRAY_SIZE);

    //Calls LinearSearch 
    LinearSearch(arr, ARRAY_SIZE, searchValue);

    // Calls BinarySearch function 
    BinarySearch(arr, ARRAY_SIZE, searchValue);


    return 0;

}

void FillArray(int arr[], int elements)
{
    // Fills array from 1 to number of elements
    for(int i=1; i<=elements; i++)
        arr[i-1] = i;
}

int LinearSearch(int arr[], int elements, int searchValue)
{
    for(int i=0; i<elements; i++)
        if(arr[i]==searchValue)
            cout << "Number of checks taken for Linear Search: " << i+1 << endl;
            // Number of checks is one more than i, since i starts with 0;
            // if you want to know the index, return i.


}

int BinarySearch (int arr[], int elements, int searchValue)
  {
      int low = 0;
      int high = elements-1;
      int mid; 
      int checks = 0; // counts number of checks taken

        // keep looping until low and high cross-over
      while(low <= high)
      {
        // makes new mid with each loop as high and low change
          mid = (low + high)/2;

        checks++; // increments with each loop

          if(searchValue > arr[mid])
              low = mid + 1;

          else if(searchValue < arr[mid])
              high = mid - 1;


          else if (searchValue == arr[mid])
            break;
      }

      cout << "Number of checks taken for Binary Search: " << checks << endl;

  }

As you can see, I fill in the array starting from 1.

Now if I enter in 5000 for the array size, and 4785 as the value im searching for, I get the following results:

Enter in size of array: 5000
Enter in a number between 0 and 5000 to search for: 4785

Number of checks taken for Linear Search: 4785
Number of checks taken for Binary Search: 8


But if I change the fill array function so the values in the array start from 0, like this:

void FillArray(int arr[], int elements)
{
    // Fills array from 0 to number of elements-1
    for(int i=0; i<elements; i++)
        arr[i] = i;
}

This now gives me a completely different result for binary search:

Enter in size of array: 5000
Enter in a number between 0 and 5000 to search for: 4785

Number of checks taken for Linear Search: 4786
Number of checks taken for Binary Search: 12


Binary checks jumped from 8 to 12? How is that possible. All I did was change the array so it had values from 0-4999 instead of 1-5000. I expected the increase of one in the linear search, but I dont understand how the binary search increased by 4.

Any ideas?

[helios]

[code]
#include <iostream>
#include <sstream>
#include <string>

std::string bin(int elements, int search){
int low = 0;
int high = elements - 1;

std::stringstream ret;
while (low <= high){
int mid = (low + high)/2;
int value = mid + 1;
ret << "arr[(" << low << " + " << high << ")/2] = " << value << "\n";
if (search > value){
low = mid + 1;
}else if (search < value){
high = mid - 1;
}else if (search == value)
break;
}
return ret.str();
}

int main(){
std::cout
<< "Sequence for 4784:\n" << bin(5000, 4784)
<< "Sequence for 4785:\n" << bin(5000, 4785)
<< "Sequence for 4786:\n" << bin(5000, 4786);
return 0;
}
[code]Output:
Sequence for 4784:
arr[(0 + 4999)/2] = 2500
arr[(2500 + 4999)/2] = 3750
arr[(3750 + 4999)/2] = 4375
arr[(4375 + 4999)/2] = 4688
arr[(4688 + 4999)/2] = 4844
arr[(4688 + 4842)/2] = 4766
arr[(4766 + 4842)/2] = 4805
arr[(4766 + 4803)/2] = 4785
arr[(4766 + 4783)/2] = 4775
arr[(4775 + 4783)/2] = 4780
arr[(4780 + 4783)/2] = 4782
arr[(4782 + 4783)/2] = 4783
arr[(4783 + 4783)/2] = 4784
Sequence for 4785:
arr[(0 + 4999)/2] = 2500
arr[(2500 + 4999)/2] = 3750
arr[(3750 + 4999)/2] = 4375
arr[(4375 + 4999)/2] = 4688
arr[(4688 + 4999)/2] = 4844
arr[(4688 + 4842)/2] = 4766
arr[(4766 + 4842)/2] = 4805
arr[(4766 + 4803)/2] = 4785
Sequence for 4786:
arr[(0 + 4999)/2] = 2500
arr[(2500 + 4999)/2] = 3750
arr[(3750 + 4999)/2] = 4375
arr[(4375 + 4999)/2] = 4688
arr[(4688 + 4999)/2] = 4844
arr[(4688 + 4842)/2] = 4766
arr[(4766 + 4842)/2] = 4805
arr[(4766 + 4803)/2] = 4785
arr[(4785 + 4803)/2] = 4795
arr[(4785 + 4793)/2] = 4790
arr[(4785 + 4788)/2] = 4787
arr[(4785 + 4785)/2] = 4786

Once the algorithm reaches mid = (4766 + 4803)/2, to move to the next or previous item it can only advance by moving around low and high. Note how the the next closest items to the algorithm from 4785 are not 4784 and 4786, but 4775 and 4795.