473,573 Members | 4,482 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

ArrayList BinarySearch vs Contains

Which is better to use with an ArrayList: BinarySearch or Contains?

The list is only going to have strings in it and it will be sorted.

Thanks,

Tom
Nov 10 '06 #1
43 6983
"tshad" <ts**********@f tsolutions.comw rote in message
news:u8******** ******@TK2MSFTN GP04.phx.gbl...
Which is better to use with an ArrayList: BinarySearch or Contains?

The list is only going to have strings in it and it will be sorted.
Then BinarySearch is better. Contains will be an O(n) operation always
(since it doesn't know whether the data is sorted), while BinarySearch is an
O(lg(n)) operation. Just make sure that the data really is sorted!

-cd
Nov 10 '06 #2
"tshad" <ts**********@f tsolutions.comw rote in message
news:u8******** ******@TK2MSFTN GP04.phx.gbl...
Which is better to use with an ArrayList: BinarySearch or Contains?

The list is only going to have strings in it and it will be sorted.
Contains is O(n)
BinarySearch is O(log(n))

For small collections Contains is probably faster
For large collections BinarySearch is Faster

If you are frequently looking for data near the front of the collection
Contains might have an edge

In short, it depends on the number of items and normal usage.

Hope this helps
Bill
Nov 10 '06 #3
"Carl Daniel [VC++ MVP]" <cp************ *************** **@mvps.org.nos pam>
wrote in message news:O9******** ******@TK2MSFTN GP03.phx.gbl...
"tshad" <ts**********@f tsolutions.comw rote in message
news:u8******** ******@TK2MSFTN GP04.phx.gbl...
>Which is better to use with an ArrayList: BinarySearch or Contains?

The list is only going to have strings in it and it will be sorted.

Then BinarySearch is better. Contains will be an O(n) operation always
(since it doesn't know whether the data is sorted), while BinarySearch is
an O(lg(n)) operation. Just make sure that the data really is sorted!
What does O(n) and O(lg(n)) mean?

Thanks,

Tom
Nov 10 '06 #4
"tshad" <ts**********@f tsolutions.comw rote in message
news:eF******** ******@TK2MSFTN GP03.phx.gbl...
What does O(n) and O(lg(n)) mean?
This question popped up just this week.
Here was my answer
If memory serves correctly the O stands for 'Order'.
Thus O(n) would be called "Order n" and O(n^2) would be "Order n
squared".
This is a measure of how efficient a given algorithm performs.
Technically it is a measure of the asymptotic behavior as the number of
elements gets very large, but, it often is appropriate even for fairly
small collections.

O(1) means that this operation takes a constant amount of time
independent of the number of items involved. A hashtable retrieval is an
O(1) operation

O(n) means that an operation takes a time proportional to the number of
elements (n). If an collection has twice as many elements, the operation
takes twice as long. A linear search is an O(n) operation

others include
O(n^2) : Goes as n*n (not very efficient for large collections)
O(log(n)): goes as the logarithm of the number of elements
O(n*log(n)) : you get the idea.

Hope this helps
Bill

Nov 10 '06 #5
"tshad" <ts**********@f tsolutions.comw rote in message
news:eF******** ******@TK2MSFTN GP03.phx.gbl...
What does O(n) and O(lg(n)) mean?
It's a Computer Science way of describing the complexity or cost of an
algorithm. The "n" relates to the size of the data, the "O" is read "order"
and the actual function describes how the length of the operation varies
according to the length of the data given the operation.

In this particular case, O(n) refers to the fact that a straight linear
search through the data will always take an amount of time that is directly
proportional to the size of the data, and increases linearly as the size of
the data increases. On the other hand, the BinarySearch method takes
advantage of the fact that the data is sorted, allowing a search for a
particular data item to increase in time proportional to log(n). Since
log(n) is always much smaller than n itself, this means BinarySearch is much
more efficient, on average.

If you intend to do any serious programming, especially where performance is
an issue, you would do well to find a good textbook or other reference on
algorithms and learn not only about the concept of "order", but also what
common algorithms have what order and how the order is affected by the data
(for example, the average case for a binary search is O(log(n)), but
depending on how the data is stored the worst case might wind up being O(n)
anyway).

Pete
Nov 10 '06 #6
Hi Tom,

"Big O Notation"
http://en.wikipedia.org/wiki/Big_o_notation

Basically you can think of it as the "n"umber of "O"peration s that is the
worst-case scenario to find the specified item in the list.

e.g., if you have 10 items in the list then the worst case in a linear search
would be O(n). This means that the worst case scenario would be examining
every item in the list (10 operations). The worst-case in a binary search
would be O(lg(n)). Binary logarithm of 10 operations. Binary log is the
worst case scenario because a binary search cuts the list in half, then
performs the same operation again on the half that contains the search item.
The pattern is continued until only one or zero items remain. If the list
isn't sorted properly than the search may fail because the algorithm might
chose the "wrong" half in which to continue searching after comparing the
current item to the search item.

"Binary Logarithm"
http://en.wikipedia.org/wiki/Binary_logarithm

"Binary Search"
http://en.wikipedia.org/wiki/Binary_search

--
Dave Sexton

"tshad" <ts**********@f tsolutions.comw rote in message
news:eF******** ******@TK2MSFTN GP03.phx.gbl...
"Carl Daniel [VC++ MVP]" <cp************ *************** **@mvps.org.nos pam>
wrote in message news:O9******** ******@TK2MSFTN GP03.phx.gbl...
>"tshad" <ts**********@f tsolutions.comw rote in message
news:u8******* *******@TK2MSFT NGP04.phx.gbl.. .
>>Which is better to use with an ArrayList: BinarySearch or Contains?

The list is only going to have strings in it and it will be sorted.

Then BinarySearch is better. Contains will be an O(n) operation always
(since it doesn't know whether the data is sorted), while BinarySearch is
an O(lg(n)) operation. Just make sure that the data really is sorted!

What does O(n) and O(lg(n)) mean?

Thanks,

Tom

Nov 10 '06 #7
"Dave Sexton" <dave@jwa[remove.this]online.comwrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..
e.g., if you have 10 items in the list then the worst case in a linear
search would be O(n). This means that the worst case scenario would be
examining every item in the list (10 operations). The worst-case in a
binary search would be O(lg(n)).
Note:

"Order" stated by itself is almost always for *average* performance, not
worst-case. One would normally specify explicitly if describing the
worst-case order for an algorithm.

For example, it is NOT true that "the worst-case in a binary search would be
O(log(n))" for all implementations of a binary search. If you have a sorted
array, it's true that the worst case is O(log(n)). However, if you have a
binary tree, a search on that tree could be as bad as O(n).

Pete
Nov 11 '06 #8
Hi Peter,

My interpretation of the wikipedia articles is obviously off a little. I
thought O notation always represented worst-case, so thanks for correcting me.
I guess it's just a fluke that I analyzed the two cases that actually are
expressing the worst-cases :)

--
Dave Sexton

"Peter Duniho" <Np*********@Nn OwSlPiAnMk.comw rote in message
news:12******** *****@corp.supe rnews.com...
"Dave Sexton" <dave@jwa[remove.this]online.comwrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..
>e.g., if you have 10 items in the list then the worst case in a linear
search would be O(n). This means that the worst case scenario would be
examining every item in the list (10 operations). The worst-case in a
binary search would be O(lg(n)).

Note:

"Order" stated by itself is almost always for *average* performance, not
worst-case. One would normally specify explicitly if describing the
worst-case order for an algorithm.

For example, it is NOT true that "the worst-case in a binary search would be
O(log(n))" for all implementations of a binary search. If you have a sorted
array, it's true that the worst case is O(log(n)). However, if you have a
binary tree, a search on that tree could be as bad as O(n).

Pete

Nov 11 '06 #9
"Dave Sexton" <dave@jwa[remove.this]online.comwrote in message
news:Ot******** ******@TK2MSFTN GP02.phx.gbl...
My interpretation of the wikipedia articles is obviously off a little. I
thought O notation always represented worst-case, so thanks for correcting
me.
I just took a look at the article you referenced. Wow. They sure didn't
cover in that kind of detail in my CS classes way back when. :) Anyway, I
can see where the confusion comes from, since the phrase "asymptotic upper
bound" could be read to imply "worst case" (the "upper bound" certainly has
that implication in daily usage). I can't say as I blame you for reading it
that way.

That's what we lowly programmers get for using the same concept that those
high-falutin' "algorithm scientists" use. :)
I guess it's just a fluke that I analyzed the two cases that actually are
expressing the worst-cases :)
I guess. Though, to be fair, in those two cases the order of the average
case is the same as the order of the worst case (if one assumes a binary
search on an array, which seems reasonable given this thread). So the
distinction is entirely academic. :)

Pete
Nov 11 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
3895
by: Eric Eggermann | last post by:
I'm going batty trying to figure out why this is not working. I'm trying to find all objects within a class derived from CollectionBase which meet a certain criteria, but the search seems to be skipping some objects. The following code is supposed to start searching the InnerList from the beginning, and continue searching while there are...
4
1301
by: Bernie Yaeger | last post by:
I'm having difficulty searching an arraylist for certain values that are in another arraylist. Essentially, I want to load the second arraylist with only one of each of the possible elements in the first arraylist. Thus if singlearraylist contains "ww", "l2", "s1", "ww", "cc", "s1" I only want marraylist to have "ww", "l2", "s1", "cc". The...
4
1515
by: Mike Dole | last post by:
I have an arraylist like the one with the Guitar Class sample in Q316302. Dim MycolliCol as arraylist Private Sub FillArray() MyColliCol.Add(New Colli(1, "STUK", 0)) MyColliCol.Add(New Colli(16, "ROL", 1)) MyColliCol.Add(New Colli(17, "BOS", 2)) MyColliCol.Add(New Colli(18, "DOOS", 0)) MyColliCol.Add(New Colli(19, "PAK", 0))
5
1541
by: Adda | last post by:
In a Parent mdi form I have a datagrid. I select a record from the grid and then invoke a childmdi form. I add the childmdi to an arraylist to keep track of it. If a user has selected multiple records from the grid and has multiple childmdi forms open and then re-selects a previously selected record, I want to activate that childmdi form....
9
2864
by: Paul Nations | last post by:
I've got arraylists of simple classes bound to controls. I need to search through those arraylists to set the correct SelectedItem in the control. The code looks like: Public Class DegreeMaintenance Private arrCipCodes As New ArrayList 'populate reader with data With rdr Do While .Read arrCipCodes.Add(New CipCode(.GetString(0),...
10
9655
by: JohnR | last post by:
I have an arraylist of string values. I would like to search the arraylist to find the index of a particular string and I would like the search to be case insensitive. dim al as new arraylist al.add("one") al.add("two") dim x as integer = al.indexof("ONE") I would like this to find the match and return 0
1
1884
by: garyusenet | last post by:
My Array list contains a collection of InternetExplorer object. One of properties of this object is HWND. I'm trying to search my arraylist for the InternetExplorer object that has a certain value for its HWND property. But i don't know the syntax to use. I have tried many things, the latest I have tried is: -
3
3089
by: Justin | last post by:
Here's a quick rundown of what I'm doing. I'm filling an arraylist with data. Then I loop through a dataset and grab a field to perform a search on the arraylist. Every time I find a match I update another field with a 1. If I don't find a match I update it with a 0. I then remove that item from the arraylist and move on. The end result...
8
2582
by: Guy | last post by:
Is there a better way to search identical elements in a sorted array list than the following: iIndex = Array.BinarySearch( m_Array, 0, m_Array.Count, aSearchedObject ); aFoundObject= m_Array; m_ResultArray.Add ( aFoundObject);
0
7741
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7661
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7978
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8167
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7730
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8028
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
1
5550
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
1
2164
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1263
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.