Binary Search in C, infinite looping?

[2FA]

I've been looking at my homework for my class and I can't get my binary search code. When the program is executed, it gets stuck on the binary search even if the array of numbers being search is small such as 10 values.

bool binary_search(int *array, int size, int val, int *comps, int *swaps) {

    bool found = false;
	int L = 0;
	int R = size - 1;
	int cnt = 0;

	while(L <= R) {

		int M = (R - L)/2;
		cnt++;
		if(val == array[M]) {
			break;
		}
		else if(val < array[M]) {

			R = M - 1;
		}
		else {

			L = M + 1;
		}
	}
    comp(val, array[0], comps);
    return(found);
}

static int comp(int a, int b, int *comps) {
    (*comps)++;

    return (a - b);
}

A few parts of the code aren't being used entirely yet but it should still be functional.

[bgibbz]

You shouldn't declare M inside of a while loop. That may be the issue. 

[gtx1060=value]

int m should be declared outside the loop and at the beginning of the program - c isn't very enjoyable to learn  

[Pinguinsan]

15 minutes ago, DeadEyePsycho said:

I've been looking at my homework for my class and I can't get my binary search code. When the program is executed, it gets stuck on the binary search even if the array of numbers being search is small such as 10 values.

bool binary_search(int *array, int size, int val, int *comps, int *swaps) {

    bool found = false;
	int L = 0;
	int R = size - 1;
	int cnt = 0;

	while(L <= R) {

		int M = (R - L)/2;
		cnt++;
		if(val == array[M]) {
			break;
		}
		else if(val < array[M]) {

			R = M - 1;
		}
		else {

			L = M + 1;
		}
	}
    comp(val, array[0], comps);
    return(found);
}

static int comp(int a, int b, int *comps) {
    (*comps)++;

    return (a - b);
}

A few parts of the code aren't being used entirely yet but it should still be functional.

Can you post your test code for this function (main.cpp)? That would help me try to work though it.

[2FA]

4 minutes ago, Pinguinsan said:

Can you post your test code for this function (main.cpp)? That would help me try to work though it.

It's actually just plain C. There is a lot of unrelated code that is uncommented so I don't really want to post all of it.

 

8 minutes ago, bgibbz said:

You shouldn't declare M inside of a while loop. That may be the issue. 

 

6 minutes ago, gtx1060=value said:

int m should be declared outside the loop and at the beginning of the program - c isn't very enjoyable to learn  

It actually doesn't matter as it will only exist inside the while loop's scope which is what I learned from my professor. In fact, he actually wrote that part himself.

 

Something I noticed while testing different array sizes. If the size of the array is larger than 22, it the program will hang/go on infinitely.

 

[reniat]

20 minutes ago, bgibbz said:

You shouldn't declare M inside of a while loop. That may be the issue. 

 

18 minutes ago, gtx1060=value said:

int m should be declared outside the loop and at the beginning of the program - c isn't very enjoyable to learn  

that's good practice, and they should do that, but that's not causing the infinite loop here.

 

@DeadEyePsycho consider the case where L = R. M should be equal to both of them, since if they are pointing at the same part, then this is the last element to check. Instead, you've got M = (L-R)/2 = 0/2 = 0. In other words, when this happens your M is going to be incorrect. What might you do to correct this? can you see the issue?

[2FA]

3 minutes ago, reniat said:

 

that's good practice, and they should do that, but that's not causing the infinite loop here.

 

consider the case where L = R. M should be equal to both of them, since if they are pointing at the same part, then this is the last element to check. Instead, you've got M = (L-R)/2 = 0/2 = 0. In other words, when this happens your M is going to be incorrect.

 

I considered there might be something with my condition but I never really put thought into it, unfortunately. Thank you so much for pointing it out.

[reniat]

Just now, DeadEyePsycho said:

I considered there might be something with my condition but I never really put thought into it, unfortunately. Thank you so much for pointing it out.

no problem  For logic issues like this, setting breakpoints and doing some step-through debugging will make the issue glaringly obvious, since you can go check values on the fly in each loop and determine which variable is causing a conditional or loop to behave differently than you'd expect. If you're not using an IDE where you can set breakpoints, try going through the loop by hand doing everything exactly as the code would do, writing down the values for each variable in each iteration. This is way more time consuming, but it works for homework. In the real world you'll nearly always have a debugger. 

[Blade of Grass]

17 hours ago, DeadEyePsycho said:

I considered there might be something with my condition but I never really put thought into it, unfortunately. Thank you so much for pointing it out.

The issue is in the way that you calculate M (you also never change the value of found, but that's irrelevant to your current error). Simple change it to (L + R) / 2 and the infinite loop no longer persists.

 

[2FA]

2 hours ago, Blade of Grass said:

The issue is in the way that you calculate M (you also never change the value of found, but that's irrelevant to your current error). Simple change it to (L + R) / 2 and the infinite loop no longer persists.

 

 

I'm aware of the found not changing. This specific bit of code was originally supposed to change it to true. Technically I'm searching for multiples of 3 up to three times the size of the array. The way I implemented the call to this function in main made it easier to just use a break instead of using a boolean.

[Ximalas]

On 28.3.2017 at 2:46 AM, DeadEyePsycho said:

I've been looking at my homework for my class and I can't get my binary search code. When the program is executed, it gets stuck on the binary search even if the array of numbers being search is small such as 10 values.

bool binary_search(int *array, int size, int val, int *comps, int *swaps) {

    bool found = false;
	int L = 0;
	int R = size - 1;
	int cnt = 0;

	while(L <= R) {

		int M = (R - L)/2;
		cnt++;
		if(val == array[M]) {
			break;
		}
		else if(val < array[M]) {

			R = M - 1;
		}
		else {

			L = M + 1;
		}
	}
    comp(val, array[0], comps);
    return(found);
}

static int comp(int a, int b, int *comps) {
    (*comps)++;

    return (a - b);
}

A few parts of the code aren't being used entirely yet but it should still be functional.

When you find what your looking for, you never set found to true.

M should be changed to:

int M = (L + R) / 2;

 

Next, your last else should really be:

else if (val > array[M])

 

Edited April 27, 2017 by Ximalas
Significant typo in my sample code. Also, forgot to mention how to compute M.

[Ximalas]

On 28.3.2017 at 3:00 AM, bgibbz said:

You shouldn't declare M inside of a while loop. That may be the issue. 

Yes and no, but mostly no. The variable M is declared at the beginning of a new block. C has allowed this for a long time. C++ allows variables to be declared when needed, and in fact encourages this style. The variable M is only needed within the scope of the while loop.

[2FA]

4 minutes ago, Ximalas said:

When you find what your looking for, you never set found to true.

 

Next, your last else should really be:

 

else if (val > array[m])

 

 

Hum, how do I specify what language the syntax highlighting should use?

 

This was a month ago and that wasn't even the issue as was pointed out. For the context of the homework, it didn't matter whether or not the value was specifically found, it was to test the performance difference between a binary and linear search by counting the amount of comparisons done in each search method. The code as I implemented during testing was functional and those discrepancies didn't matter for that purpose. I was only asking about the looping issue.

[Ximalas]

5 minutes ago, DeadEyePsycho said:

This was a month ago and that wasn't even the issue as was pointed out. For the context of the homework, it didn't matter whether or not the value was specifically found, it was to test the performance difference between a binary and linear search by counting the amount of comparisons done in each search method. The code as I implemented during testing was functional and those discrepancies didn't matter for that purpose. I was only asking about the looping issue.

My bad. I forgot to check the date.