binsearch does not work in sorted array?

binsearch does not work in sorted array? - Printable Version

+- SA-MP Forums Archive (https://sampforum.blast.hk)
+-- Forum: SA-MP Scripting and Plugins (https://sampforum.blast.hk/forumdisplay.php?fid=8)
+--- Forum: Scripting Help (https://sampforum.blast.hk/forumdisplay.php?fid=12)
+--- Thread: binsearch does not work in sorted array? (/showthread.php?tid=630523)

binsearch does not work in sorted array? - faxxe - 15.03.2017

Ahoy friends.

I have created 2 Arrays by this way

Код:

new ActorPickups[sizeof(GlobalActors)];
new MoneyPickups[MAX_PICKUPS-sizeof(GlobalActors)-1];

and defined Pickup types

Код:

enum
{
	INVALID_PICKUP_TYPE,
	MONEY_TYPE,
	ACTOR_TYPE
};

I put the pickupids into the MoneyPickup array

Код:

stock GenerateRandomPickup(modelid,type,Float:x_max,Float:x_min,Float:y_max,Float:y_min,Float:z_max,Float:z_min,virtualworld)
{
	if(maxmoney <= sizeof(MoneyPickups))
	{
		moneyval= moneyval+1000;
		new Float:rx1=((frandom((floatabs(x_max-x_min)))+x_min));
		new Float:ry2=((frandom((floatabs(y_max-y_min)))+y_min));
		new Float:rz3=((frandom((floatabs(z_max-z_min)))+z_min));
		maxmoney = maxmoney +1;
		MoneyPickups[maxmoney] = CreatePickup(modelid,type,rx1,ry2,rz3,virtualworld);
		printf("%d,%d,%f,%f,%f,%d",modelid,type,rx1,ry2,rz3,virtualworld);
		
	}


}

If i pickup a moneypickup OnPlayerPickUp will be called

Код:


public OnPlayerPickUpPickup(playerid, pickupid)
{
	new index;
	switch(GetPickupType(pickupid,index))
	{
	case INVALID_PICKUP_TYPE:
		{
		}
	case MONEY_TYPE:
		{
			maxmoney -= 1;
			GivePlayerMoney(playerid, 1000);
			printf("ID picked up: %d",maxmoney);
			MoneyPickups[index]=-1;
			HeapSort(MoneyPickups);
			DestroyPickup(pickupid);
		}
	case ACTOR_TYPE:
		{
			ShowMenuForPlayer(shopmenu,playerid);
			TogglePlayerControllable(playerid,false);
		}
	}
	return 1;
}

GetPickUpType will be called

Код:

stock GetPickupType(pickupid, &index)
{
		new mres = binsearch(MoneyPickups,pickupid,sizeof(ActorPickups)-1,sizeof(MoneyPickups)-1);
		if(MoneyPickups[mres] == pickupid) return index=mres,MONEY_TYPE;
		printf("ID:%d mres: %d",pickupid,mres);
	
		new ares = binsearch(ActorPickups,pickupid,0,sizeof(ActorPickups)-1);
		if(ActorPickups[ares] == pickupid) return index=ares,ACTOR_TYPE;
		printf("ID:%d mres: %d",pickupid,mres);
	
	return INVALID_PICKUP_TYPE;
}

But for some reason the binary search in the first case (Money Type) is never successful.
It works for ActorPickups arrays in case of actor pickups, but not for money pickups for some reason.

After picking up a MONEY_TYPE Pickup the array will be sorted by using heap sort

But for some reason the search process in the MoneyPickups array is never successful
Whats the problem?

Код:

stock HeapSort (array [], n = sizeof (array))
{
	new i;
	for (i = n / 2; i > 0; --i) // Make heap
	SinkDown (array, i, n);

	for (i = n; i > 1; --i)
	{
		Swap (array [i - 1], array [0]);
		SinkDown (array, 1, i - 1);
	}
}

//----------------------------------------------------------

static stock SinkDown (array [], i, m)
{
	new j;
	while (2 * i <= m)
	{
		j = 2 * i;
		if (j < m && array [j - 1] < array [j])
		++j;
		
		if (array [i - 1] < array [j - 1])
		{
			Swap (array [i - 1], array [j - 1]);
			i = j;
		}
		else
		i = m;
	}
}

//----------------------------------------------------------

static stock Swap (&a, &b)
{
	new s;
	s = a;
	a = b;
	b = s;
}

I also tried this

Код:

new mres = binsearch(MoneyPickups,pickupid,sizeof(ActorPickups)-1,MAX_PICKUPS-sizeof(GlobalActors)-1);

but it didnt work as well

My binsearch function

Код:

stock binsearch(a[],key,l,r)
{
	new k;
	while(r >=l)
	{
		
		k = (l+r)/2;
		if(key == a[k])
		{
			return k;
		}
		if(key < a[k]) 
		{
		r = k=1;
		}
		else 
		{	
		l= k+1;
		}		
	}	
	return 0;
}

Re: binsearch does not work in sorted array? - SyS - 15.03.2017

if(key < a[k])
{
r = k-1;
}