Find a string in a JavaSscript array

[Sanada]

I'm hoping there're some JavaScripts pros here that can help me with this problem.

I have an array on strings that look something like this:

	var ref_array = new Array();
	ref_array[0] = "107348556";
	ref_array[1] = "107999024";
	ref_array[2] = "143687952";
	ref_array[3] = "102487924";

This array contains reference numbers and would, in time, become very big. The data for the array is extracted from a SQL database using PHP code. This is what it looks like in the generated web file file.

What I'd like to do now is use an onChange event on a input text field to trigger a function that creates a pop up a alert message if the 9-digit number entered matches one in the array. So, if I enetered the number "107348556", a alert message should appear. I've tried various code snippets from the web but none work. I usually end up getting a "Object expected" error in the debug window in IE (I have tested in 3 other browsers and get the same thing).

 

[Druckles]

Can you not loop through the array and simply compare the inputted string with each item?

 

[PvtRyan]

If speed is a concern with looping through a big list, you could consider using a Dictionary/Hashtable implementation for Javascript, those tend to be faster than a simple for-loop. I'm sure there are implementations out there, or perhaps it has a Dictionary class of its own, I'm not really at home in Javascript.

 

[DreamThrall]

If what you're trying to do is anything but academic, and is used for any sort of authentication, you don't want to do it in JavaScript.

JavaScript doesn't have a native hashtable type class as far as I know, but I'm sure there are loads of array scanning algorithms available.

 

[Sanada]

I'm making a booking-in type system where details of items are entered and then stored into a SQL database. All I'm using the JavaScript for is additional client side validation on top of the server side validation. Data integrity is a top priority so if it does pose a threat to it I'd have to remove it.

I did decide to use a for loop in the end to check the numbers using the array indexes but now I'm concern about what happens when the array grows larger and the performance hit it could cause. Bandwidth won't really be an issue as it's being used over a LAN. At the moment it's small <100 but it will grow to 1000's in time. I may just have to scrap it all together as it's not essential to the functionality, just something to save time and be more convenient for the user.

If what you're trying to do is anything but academic, and is used for any sort of authentication, you don't want to do it in JavaScript.

JavaScript doesn't have a native hashtable type class as far as I know, but I'm sure there are loads of array scanning algorithms available.

If JavaScript is not very good/suitable what else could be used for client side validation? I have looked around for array scanning algorithms but couldn't get any of them to work.

EDIT: I've looked into it more and the only other method I can find is to convert the whole array to one long string and then simple search that string. However, the search() function in JavaScript function will still return a posistive value if it finds a match for a single character. So, if I wanted to search for "Hello", it'd still return a posistive value if I just searched for "e". I want it to only return a posistive value if it finds the complete "Hello" string.

 

[DreamThrall]

If JavaScript is not very good/suitable what else could be used for client side validation? I have looked around for array scanning algorithms but couldn't get any of them to work.

Validation != authentication. If all you're doing is making sure a given value is valid for a specific entry in a form, then JavaScript is the way to go. However, if the value is an account number or anything else to do with authentication (ie, allowing a user to log in) do not, by any means, put it in JavaScript. It is way too easy for anyone to just look at the JavaScript and see what the valid values are, or even bypass the authentication altogether using any console that can execute arbitrary script on a page (like FireBug).

Authentication should *always* be done server-side.

EDIT: Are you looking for specific values or a specific pattern? If the data falls into a pattern, just use regex.

EDIT2: Even if your array is several thousand large, I don't think looping through would even be that bad. If you were doing recursive loops, or got up into the 100k range, that would become an issue ... but if all you're doing is a compare on a couple thousand values, you'd be surprised how fast that happens.

 

[Sanada]

The data isn't anything sensitive like account numbers or anything. I just need this script to prevent duplicate entries from being made as the numbers must be unique. The server side validation would stop it from happening anyway but I thought I'd be nicer if the user could be told before submitting the form.

If looping through thosands of values isn't to bad then I guess the current method will do. It would take years for it reach like 100K+ so I guess it doesn't matter. The data would be made redundant after that time anyway and the database could be reset.

 

[DreamThrall]

so I've never actually written a binary search function before and I got curious, so I wrote one:

Array.prototype.contains = function(value) {
	// *************ElementById('output').value = ''; // for testing
	
	var attempts = 0;			// to track the number of attempts
	var index = 0;				// the index of the array to check
	var lbound = 0;				// the lower bound of the search
	var ubound = this.length;	// the upper bound of the search
	
	while(true) {
	
		// calculate the new index, which is the average of the upper and lower bounds of the search
		index = Math.floor((ubound + lbound) / 2);
		
		// if the new index is equal to the upper bound, we know that the value doesn't exist in this array
		if(index == ubound) return false;
		
		// get the value for the new index
		result = this[index];
		
		attempts++;	
		// *************ElementById('output').value += 'attempt\t'+attempts+':\tindex:\t'+index+'\tlbound:\t'+lbound+'\tubound:\t'+ubound+'\tresult:\t'+result+'\n'; // for testing
		
		if(result == value) return true;
		
		// if we didn't find the value, narrow the search to exclude the the parts we know do not contain the value
		else if(result < value) lbound = index;
		else /*if(result > value)*/ ubound = index;		
		
		// this shouldn't happen, but it's here just to prevent an infinite loop just in case.
		if(attempts > this.length) return false;
	}
}

Usage:

var numbers = new Array(
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
13,
14,
15,
16,
17,
18,
19,
20
);

alert(numbers.contains(8));

I make no guarantees about this function - it worked correctly in FireFox when I tested looking for 8, 0, 1, 20 and 21. You might want to test it out in IE because I believe it sometimes has issues with adding to the prototype for base classes. Also, feel free to cut out the comments and whitespace - I just put that in there to make it easier to read.

Regardless, just searching for 8 returned true in 4 iterations (rather than 8), so this will be literally exponentially faster than doing a flat search.

Here's some basic info about search alogrithms: http://research.cs.queensu.ca/home/cisc121/2006s/webnotes/search.html

EDIT: the *************ElementById in the code is document . getElementById() if you couldn't tell. I'm guessing it's filtered out by the forum.
EDIT2: If you want to see the results of each iteration, create a textarea with the id "output" and uncomment the "for testing" lines.
EDIT3: By the way, the array needs to be sorted in ascending order for this to work correctly.

 

[DreamThrall]

This warrants a new post...

We're all dumbasses because he can just use the indexOf() function... bleh :x

 

[Sanada]

I tried your script out and it works great although there was one issue with it. The strings I need to search for will be a max of 9 characters long. I changed the array to look like this to test it out.

var numbers = new Array(
888888888,
454353455,
66666666,
333333333,
105864234,
765312487
);

If I try to search for "888888888" it will return false. If I try to search for "454353455" it will return false. If I shorten it to 8 numbers long it will return true. This also made the 9 digit numbers below it return true also like they should. If I shortened the first one to 8 digits, "454353455" will return true. I tested this in Opera. I don't have IE installed so I will download either Firefox or Chrome to see if it's the same.

This warrants a new post...

We're all dumbasses because he can just use the indexOf() function... bleh :x

That's not nessesarily true. I tried indexOf() but it's no good to me. It only returns the posistion of the first instance of the string. So If I had "123456789" and searched for "4" it'll return 4 or 5. I only want it to return true/positive if the whole string is found and not a single part of it.

 

[Druckles]

Convert the value "-1" into false and anything else into true.

Voila.

 

[DreamThrall]

I didn't mean indexOf() on the string, I meant on the array.

If I try to search for "888888888" it will return false. If I try to search for "454353455" it will return false. If I shorten it to 8 numbers long it will return true.

That's because:

EDIT3: By the way, the array needs to be sorted in ascending order for this to work correctly.

var numbers = new Array(
66666666,
105864234,
333333333,
454353455,
765312487,
888888888
);

or:

var numbers = new Array(
888888888,
454353455,
66666666,
333333333,
105864234,
765312487
);
numbers.sort();

Though, if you're generating it from a php script, it'll be much more performant on the client to just sort the list in your mysql query first.

EDIT:

Not that it matters because it's easier to just use indexOf(), but here's a modification to my contains() function that will automatically sort before searching:

Array.prototype.wasSorted = false;

Array.prototype.contains = function(value) {
	// *************ElementById('output').value = ''; // for testing
	
	if(!this.wasSorted) {
		this.sort();
		this.wasSorted = true;
	}
	
	var attempts = 0;			// to track the number of attempts
	var index = 0;				// the index of the array to check
	var lbound = 0;				// the lower bound of the search
	var ubound = this.length;	// the upper bound of the search
	
	while(true) {
	
		// calculate the new index, which is the average of the upper and lower bounds of the search
		index = Math.floor((ubound + lbound) / 2);
		
		// if the new index is equal to the upper bound, we know that the value doesn't exist in this array
		if(index == ubound) return false;
		
		// get the value for the new index
		result = this[index];
		
		attempts++;	
		// *************ElementById('output').value += 'attempt\t'+attempts+':\tindex:\t'+index+'\tlbound:\t'+lbound+'\tubound:\t'+ubound+'\tresult:\t'+result+'\n'; // for testing
		
		if(result == value) return true;
		
		// if we didn't find the value, narrow the search to exclude the the parts we know do not contain the value
		else if(result < value) lbound = index;
		else /*if(result > value)*/ ubound = index;		
		
		// this shouldn't happen, but it's here just to prevent an infinite loop just in case.
		if(attempts > this.length) return false;
	}
}

It'll break if you call contains(), then add something without setting wasSorted to false and then call contains() again, but it'll work if you aren't messing with the array after it is instantiated.

 

[Sanada]

Opps, I didn't see that last bit about them needing to be sorted. Speaking of that, would it speed up the searching of the array if they were in ascending order or will it make no difference (if the array was quite large of course)?.

Anyway, I've just found out why indexOf wasn't working for me before. Turns out it was something wrong with IE6 (figures) as it works fine in Chrome. Guess I shouldn't use it for development but my <tables> don't look right in any other browser.

I really appreciate the help from you all. I'm slowly getting the hand of JavaScript a bit more know.

 

[DreamThrall]

Well I'm guessing that indexOf() does something similar to the code I posted, and if that's the case, then probably yes because otherwise it will have to sort it itself. Of course, it's possible that it will sort regardless... If you want to be sure go ahead and test it.

 

[No Limit]

Why not store the codes on the server and simply use a AJAX call to check if that code exists? If you are using php the in_array function would work fine for you:

http://us3.php.net/function.in-array

But really if you are talking about thousands of codes you would obviously want to store them in a mysql database instead of an array and use a sql query to check if the code exists. The other plus side is people won't be able to know what codes you have by simply viewing the source of the page.

 

[Oreolek]

Authentication should *always* be done server-side.

It's a good advice and you should follow it. Use the AJAX+CGI.
Any good user can view the page source and retrieve the code.

 

[Sanada]

I know authentication should be done server-side but the data I'm dealing with isn't important enough for it to even matter if anyone can see it.

Anyway, I decided to give AJAX a go. I did try it before but looking at it gave me a headache and seemed like too much work for something so small. After hours of trying to figure why my code wasn't working, I finally got it to work properly.

All I need to do now is use it to create a dynamic drop down menu.

 

[Qhartb]

Agreed. This sort of thing is what AJAX is for.

 

[No Limit]

I know authentication should be done server-side but the data I'm dealing with isn't important enough for it to even matter if anyone can see it.

Anyway, I decided to give AJAX a go. I did try it before but looking at it gave me a headache and seemed like too much work for something so small. After hours of trying to figure why my code wasn't working, I finally got it to work properly.

All I need to do now is use it to create a dynamic drop down menu.

It's not just for authentication. If you have large amounts of data coming out of a database javascript will not be an effective way to deal with that data. If you are generating your javascript using a server side language a good rule of thumb is that you probably should use AJAX instead.

Glad you got it working. I haven't done much with Ajax at this point but from what I have done I absolutely loved it.