3

OK. I am using the C# programming language to access a simple database (on Microsoft SQL Server)

Currently, I am using the DataReader object to access the database. So here is my question: is it possible to do a binary search (in C#) for a particular piece of data so that i can make the search faster?

Currently, I'm using a simple while loop to search the contents of the database. I believe this is done sequentially.

while (pReader.Read())
{
   if ((String)pReader["theData"] == "The_thing_im_searching_for")
   break;
}

So is there any way to do a binary search?

6 Answers 6

21

If you're using a database anyways, you should write a select statement to search for what you're looking for instead of iterating through the database manually. There's no reason to reinvent the wheel.

0
6

As Donnie points out, if you express your predicate in SQL, the database will select the most efficient way of extracting your data automatically.

Try this:

string sql = "SELECT * FROM Foo WHERE theData = 'The_thing_im_searching_for'"
SqlDataAdapter adapter = new SqlDataAdapter(sql);
DataTable table = new DataTable();
adapter.Fill(table);

foreach(DataRow row in table.Rows) {
    // Do whatever you want here
}
3

In the spirit of Donnies answer, I've provided a simple SQL example of how to retrieve what you're after using a more securable mechanism than dynamically constructed SQL (as others have advised you)

In the simple case, you should create a stored procedure for each Create, Read, Update, Delete operation available to the application, per entity in the database. (This isn't 100% true in large production systems, but it's better than dynamically generated SQL constructed in the application)

Now for the READ, this lists all if no parameter is provided. This is a simplified version of an approach a database architect at my job has lectured on -- here we don't separate the retrieve stored procedure from the listing procedure, they are effectively the same operation. This will pay out in less SQL code to maintain in the long run.

CREATE PROCEDURE usp_ReadName 
 @name_id bigint=NULL
AS
BEGIN
 SET NOCOUNT ON;
 if (@name_id IS NULL)
  SELECT name_id,name,description 
            from name with(nolock)
 else
  select name_id,name,description 
            from name with(nolock) 
            where name_id = @name_id  
END
GO

Now for the C# side. To hold the results we define a data transfer entity. Generally speaking these are lighter weight than a datatable faster and more efficient to use. If speed, large volumes of data or limited memory are not a concern just go with a datatable. (On average you'll save roughly 40%+ memory, and about 10% speed - 100K records of the structure above peaks memory use at 140MB with a datatable while the DTE peaks at 78MB)

/// <summary>
/// A simple data transfer entity
/// </summary>
public struct name_data
{
    public long name_id;
    public string name;
    public string description;
    public name_data(long id, string n, string d)
    {
        name_id = id;
        name = n;
        description = d;
    }
}

Now we capture the results in C# using the nullable parameter syntax. This code assumes you've already opened the sql connection

conn.Open();
using (SqlCommand cmd = new SqlCommand("usp_ReadName",conn))
{
    cmd.CommandType = CommandType.StoredProcedure;
    if (id.HasValue)
        cmd.Parameters.Add("@name_id", SqlDbType.BigInt).Value = id.Value;
    using (SqlDataReader reader = cmd.ExecuteReader())
    {

        if (reader.HasRows)
        {
            while (reader.Read())
            {
                dte.name_data item = new dte.name_data(
                    (long)reader["name_id"],
                    reader["name"].ToString(),
                    reader["description"].ToString());
                items.Add(item);
            }
        }
    }
}
2
  • Not that the information is bad, but this is serious overkill given his statement of the simple database. Also, there is still a pretty healthy debate going on among most DB developers about the benefits of doing everything in sprocs vs client-side SQL, so I'd not be passing that off as the gospel-truth-one-true-way quite yet. :)
    – Donnie
    Nov 24, 2009 at 4:56
  • it's good to also note that I didn't say "do everything in stored procedures." I said "In the simple case you should create a stored procedure for each Create, Read, Update, Delete operation available to the application, per entity in the database." This was relative to creating more secure (i.e. from SQL injection, yes it's technically possible still if you do truly fancy stuff in a stored procedure, but that's not usually the domain of simple CRUD operations) I even went on to say that on large production systems doing CRUD operations that way wasn't always the right way.
    – Jason D
    Nov 25, 2009 at 1:37
2

Thanks for all the Information (Jay Here again). I believe i have my question answered.

The thing is, I have a lot of information in the database. Searching for a particular item would take a lot of time. So i was interested in doing a binary search.

When i do a SELECT command to find something, i do not know whether or not MSSQL (in the back ground) does a binary search. But if what RickNZ (above) says is true

The problem with a straight SELECT on the SQL Server side is that the DB will do a linear search through the table unless the column you're working with has an index on it; then the DB can be smarter.

Then the database will do the search most effeciently (a binary search) if i had the information "indexed".

0

Daniel and Donnie's responses here telling you this is a bad idea are very correct.

However, a more direct answer to your question is that yes you can search binary data, though I'm not sure this is what you are looking for.

MSSQL can store data in the varbinary format, and you can do searches on this varbinary data. In fact you can find more information on doing so in this post: Dealing with a varbinary field in VB.NET

Here's an example of a query doing just that.

byteArrayToken = StringToByteArray(stringToken)
scSelectThing.CommandText = "select thing from table where token=@token"
Dim param As SqlParameter = scSelectThing.Parameters.Add("@token", SqlDbType.VarBinary)
param.Value = byteArrayToken
lbOutput2.Text = scSelectThing.ExecuteScalar()
1
  • 3
    Props for the thorough answer, but by context of the question, I think he was referring to a "binary search algorithm" as opposed to an "algorithm to search binary data."
    – Adam Maras
    Nov 24, 2009 at 4:46
0

So is there any way to do a binary search?

The problem with a straight SELECT on the SQL Server side is that the DB will do a linear search through the table unless the column you're working with has an index on it; then the DB can be smarter.

If you need to read the entire table anyway (for example, so you can search it again a short time later), then you might consider using ArrayList.BinarySearch(). Of course, for that to work, the data will need to be in sorted order in the ArrayList.

2
  • If you're searching on the column, the solution is usually to put an index on it to prevent a full table scan(i.e. linear lookup). And as you've pointed out if you've got it all in memory it'll need to be sorted appropriately. (Or you can make liberal use of the Dictionary<T> class...) However, if someone is not using the indexes in the database and is reading all the data once and searching it in memory, I wonder why they bother with the database at all. (e.g. what if new entries of interest are added by another user, how does the app instance in question know about it?)
    – Jason D
    Nov 25, 2009 at 1:44
  • If new entries are added by another user (or another web server), you can use the SqlDependency or SqlCacheDependency classes to have SQL Server send you a notification about the change.
    – RickNZ
    Nov 25, 2009 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.