Member Avatar for Der_sed

The following binary search code runs perfect .

I feed values that exist in the array and it tells me at what location they are.

But if i enter a value non-existent in the array it goes bad.

It says number not in array and after that...

Any other value i enter after this wrong value is not in the array even thought initially it was in this array.... 

#include <iostream>
#include <cstdlib>

using namespace std;

const int arrSize = 100;  
bool isPresent(int theArr[arrSize], int n);
     
int main()
{    
    int myArr[arrSize];
    int input;
    char quit;         // input inquiry for quit or continue
    bool j;            // j is assigned the return value
    
    for (int i=0; i<=arrSize; i++)
        myArr[i]=rand();      //creating array with random numbers
    
    
        
    //sorting random numbers
    for (int j=0; j<=arrSize; j++){
        for(int k=0; k<j ; k++){        
            if (myArr[j] < myArr[k]){
               
               myArr[k] = myArr[j] + myArr[k];                       
               myArr[j] = myArr[k] - myArr[j];
               myArr[k] = myArr[k] - myArr[j];
            }
        }
    }
    
    //display array
    for (int i=0; i<=arrSize; i++)
        { cout<<myArr[i]<<" ";
          if ( i%6==0 ) cout<<endl; }
    
    
       
    while (1)
    {
    
    cout<<"\n Enter number to check in the array: \n";
    cin>>input;
    
    j= isPresent( myArr, input );
    
    if (j==1)
    cout << "Success. The item was found."<< endl;
    if ( j==0)
    cout << "The item was not in the array\n";

    
    cout<<" Do you want to check for another number?\n";
    cin>>quit;
    if ( quit=='n' || quit =='N')
    break;
    
    } 
    

    
    system("PAUSE");
    return 0;

}


// function code 


bool isPresent(int theArr[arrSize], int n)
{
     int left=0, right, mid=0;
     right = arrSize - 1;

         
         
     while (left <= right)
     {
     mid = ((left + right) / 2);
     if (n == theArr[mid])
     { cout<<"Found @ location:"<<mid<<endl;
           return 1;      }

       else if (n > theArr[mid])
     left = mid + 1;
     else
     right = mid - 1;
      }

return 0;
 // code is IP of 09030032 [at] lums   
}
Edited by Der_sed because: n/a
  • 3 Contributors
  • 4 Replies
  • 119 Views
  • 19 Hours Discussion Span
  • Latest Post Latest Post by vmanes

Dani AI

Generated

Two things are almost certainly at work here: an out‑of‑bounds write and the resulting undefined behavior. correctly flagged the loop bounds and explained why that produces a "ghost" element. Writing past the end of myArr can clobber adjacent memory (stack variables, return addresses, or other program state), so the program can behave strangely later — for example, a subsequent binary search can fail even for values that actually exist. See the language note on undefined behavior for background: Undefined behavior (C++).

Practical advice that fixes the root cause and makes the code easier to maintain:

  • Avoid raw fixed-size arrays and manual sorting/searching unless you need to. Use the STL: std::vector, std::sort, and std::binary_search or std::lower_bound (to get an index).
  • Avoid arithmetic swaps. Use std::swap (or just rely on std::sort).
  • Use size_t/constexpr for sizes, and make loop bounds explicit so off‑by‑one mistakes are less likely.

Example (modern, safer approach):

#include <vector>
#include <algorithm>
#include <cstdlib>

constexpr size_t N = 100;
std::vector<int> a(N);
std::generate(a.begin(), a.end(), std::rand);
std::sort(a.begin(), a.end());

auto it = std::lower_bound(a.begin(), a.end(), value);
if (it != a.end() && *it == value) { size_t index = std::distance(a.begin(), it); /* found */ }
else { /* not found */ }

To diagnose the original crash/behavior, run the program under AddressSanitizer or Valgrind. With g++:

g++ -std=c++17 -g -O1 -fsanitize=address,undefined -o test test.cpp
./test

AddressSanitizer will pinpoint out‑of‑bounds accesses. For cross‑platform algorithm docs and binary_search/lower_bound, see std::binary_search / std::lower_bound (cppreference).

Recommended Answers

All 4 Replies

Member Avatar for mrnutty

first this is wrong :

for (int i=0; i<=arrSize; i++)  //it should be   i < arrSize
        myArr[i]=rand();      //creating array with random numbers

The same goes for sorting and displaying numbers.

Member Avatar for vmanes

Works ok for me. And I see nothing about the search code that seem to cause any problem.

Member Avatar for mrnutty

it didn't work when first input was a negative number then the next
input was the last number in the solution grid.

Member Avatar for vmanes

go back to firstPerson's comment - what you see as the "last" element in your array is actually index 100 (item #101 !!). Your fill, sort and display go one step to far, but your search is correct, so it cannot possibly find that ghost element.

Remember, the canonical loop for walking an array is:

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

Use a strictly less than test and you'll stay safe.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.