why is my binary search not not working with my array?

Question

trying to learn some basic data structures and algorithms and ive tried to code a basic binary search but it doesn't work unless the input is the same as the middle? can anyone help?

void Search(int input) {

    int array[10] = { 0.1,2,3,4,5,6,7,8,9,10 };
    int first = array[0];
    int last = sizeof(array) / sizeof(array[0]);;
    int middle = first + last / 2;

    if (input == middle) {
        cout << "search succesful";
    }
    else if (input > middle) {
        middle + 1;
        Search(input);

    }
    else if (input < middle) {
        middle - 1;
        Search(input);

    }
}

  int main()
    {
     int input;
     cin >> input;
     Search(input);
    }

Unrelated: int array[10] = {0.1 ... that conversion is invalid — Ted Lyngmo
– Ted Lyngmo, Commented Aug 21, 2022 at 13:22
Remember that when you call a function, a brand new set of all local variables are created. That's also true for recursive calls. The middle variable of the calling function is not the same middle variable in the new call. — Some programmer dude
– Some programmer dude, Commented Aug 21, 2022 at 13:26
You don't have this problem if you implement the search within a loop instead of recursively. Still your implementation provides zero re-usability as data is included in the function itself. Better: Separate data to operate on from the operation itself and provide the former to the latter via parameter. — Aconcagua
– Aconcagua, Commented Aug 22, 2022 at 9:55

AsKreY · Accepted Answer · 2022-08-21 13:23:51Z

5

If you want to use recursion than you should also pass the right and left border of array and change them in your if statements. When you do middle-1 you don't change anything. Here is binary search implemantation

int binarySearch(int nums[], int low, int high, int target)
{
    // Base condition (search space is exhausted)
    if (low > high) {
        return -1;
    }
 
    // find the mid-value in the search space and
    // compares it with the target
 
    int mid = (low + high)/2;    // overflow can happen
    // int mid = low + (high - low)/2;
 
    // Base condition (target value is found)
    if (target == nums[mid]) {
        return mid;
    }
 
    // discard all elements in the right search space,
    // including the middle element
    else if (target < nums[mid]) {
        return binarySearch(nums, low, mid - 1, target);
    }
 
    // discard all elements in the left search space,
    // including the middle element
    else {
        return binarySearch(nums, mid + 1, high, target);
    }
}

answered Aug 21, 2022 at 13:23

AsKreY

631 silver badge6 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Aconcagua Over a year ago

As negative indices into the array are meaningless I'd prefer an unsigned type – and from C++ point of view, size_t would be the most appropriate type for indices...

Collectives™ on Stack Overflow

why is my binary search not not working with my array?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related