Binary Search Algorithm.

[MarkCode82 21]

ArmA 3 really annoys me because it lacks a dictionary data type I know you are going to direct me to the BIS_fnc_addToPairs, but there is no actual dictionary datatype in arma 3. The reason i say this is because. Binary search will allow me to traverse a large array data set much quicker than forEach array; Only problem is sorting the data which is mission specific such as town locations is not possible because attempting to sort the array will result in it's meaning lost.

 

_array = _this select 0;
_arrayCount = count _array;
_requestedElement = _this select 1;
_low = 0;
_high = _arrayCount;
while {_low <= _high} do {
//Comupute mid point
_mid = round(_low + (_high - _low) / 2);
	diag_log format ["_mid: %1",_mid];
	_indexReturn = {_x == _requestedElement} count _array;
	diag_log format ["_indexReturn: %1",_indexReturn];
	if (_requestedElement isEqualTo (_array select _mid)) then {
		_pulledData = _array select _mid;
		diag_log format ["_pulledData: %1",_pulledData];
	} else { 
		if (_indexReturn < _mid) then {
			_low = _mid + 1;
		} else {
			_high = _mid - 1;
		}
	};
};
_pulleddata

Data Pulled:
 

["Gravia",[14479.8,17614.3,-21.6749],
"Telos",[16207,17296.7,-24.3308],
"Athira",[13993,18709.4,-25.735],
"Lakka",[12282,15732.3,-23.0026],
"Frini",[14612.5,20786.7,-47.0032],
"Charkia",[18049.1,15264.1,-28.4237],
"Rodopoli",[18753.4,16597.1,-32.1656],
"Neochori",[12502,14337,-11.5868],
"Pyrgos",[16780.6,12604.5,-18.9913],
"Paros",[20885.4,16958.8,-49.8089],
"Dorida",[19336.9,13252.3,-37.8615],
"Poliakko",[10966.5,13435.3,-28.4601],
"Kalochori",[21351.6,16361.9,-20.5678],
"Agios Dionysios",[9187.95,15947.8,-124.829],
"Syrta",[8625.13,18301.6,-179.297],
"Chalkeia",[20194.6,11660.7,-45.8388],
"Zaros",[9091.81,11961.9,-19.9013],
"Kore",[7062.42,16472.1,-116.425],
"Sofia",[25680.5,21365.1,-20.7333],
"Kavala",[3458.95,12966.4,-6.1822],
"Molos",[26943.9,23170.7,-18.0848]]

Numerical keys that are sequential are required for this to work. As a binary search is best used on hash-table keys. Any know of any dictionary methods for arma 3?

[pedeathtrian 100]

Y U NO put each location in separate array item? [[String, Array], [String, Array]...] instead of [string, Array, String, Array, ...]? You can't use binary search on array you've posted above.

---

_indexReturn = {_x == _requestedElement} count _array;

This does not do what you think it does. It is not find, it's count. It returns amount of elements equal to _requestedElement, not their position. So 0 if there's no such element, or 1 if you have only one, and so on. It also have linear complexity on array's length, and is called on every while's iteration, so even if you were correctly comparing _mid to some index, it would give you N log N complexity. Why not just use find then? It has linear.

If you somehow have index of required item, you don't need the binary search already.

 

Even when you have all array items in the form [string, Array], and search using String key, you will need lessthan operator called on key values (Strings, _mid key and requested key), not indexes. And comparing strings is yet some code to call (and write).

Taking everything in account, you will need thousands of items in array to win something with binary search against simple BIS_fnc_findInPairs call.

[bull_a 44]

+1 to above

[MarkCode82 21]

private ["_locTypeArr", "_islandNamesArr"];

_locTypeArr =
[
"CityCenter",
"NameCity",
"NameCityCapital",
"NameLocal",
"NameMarine",
"NameVillage"
];

_islandNamesArr = [];
_locPosArr = [];
_locNamePosArr = [];

[_locTypeArr,[],true] call bis_fnc_locations;
_nearbyLocations = nearestLocations [getPos player, text _locTypeArr, 100000];

for "_i" from 0 to (count _nearbyLocations)-1 do {
_location = _nearbyLocations select _i;
_locationName = text _location;
_locationPos = locationPosition _location;

_locPosArr set [count _locPosArr, _locationPos];
_islandNamesArr set [count _islandNamesArr, _locationName];

_locNamePosArr set [count _locNamePosArr, _locationName];
_locNamePosArr set [count _locNamePosArr, _locationPos];

};
copyToClipboard (str (_locNamePosArr));

/* _locTypeArr =
[
"CityCenter",
"NameCity",
"NameCityCapital",
"NameLocal",
"NameMarine",
"NameVillage"
]; */

The above is the data that was generated to be searched, I counted at least 100 elements in the array.

[pedeathtrian 100]

Replace 

_locNamePosArr set [count _locNamePosArr, _locationName];
_locNamePosArr set [count _locNamePosArr, _locationPos];

with 

_locNamePosArr pushBack [_locationName, _locationPos];

and you will have your dictionary (and use BIS_fnc_findInPairs on it). Which in turn duplicates the contents of  _locPosArr  and  _islandNamesArr. You could use find on  _islandNamesArr  to find an index which you then can use in  _locPosArr  and abandon  _locNamePosArr  totally (or vice versa).

 

 

---

_nearbyLocations = nearestLocations [getPos player, text _locTypeArr, 100000];

I don't get the point of text in this line; and in general, using nearestLocations might be overkill here, and probably it's better to get everything from config. Unless you use the "sorted-by-distance" property of  nearestLocations'  return (which is invalidated the moment player starts to move).