• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 283
  • Last Modified:

Why BinarySearch return a wrong value ? ( -4)

I found this problem in my web application, then I tested the following code in a windows application, same problem.

      ArrayList list1 = new ArrayList();
      list1.Add("3");

      ArrayList list2 = new ArrayList();
      list2.Add("1" );
      list2.Add("2" );
      list2.Add("3" );

      int nIdx=list1.BinarySearch("3");

      for ( int j=0 ; j< list2.Count;j++)
      {
            string strNew= (string)list2[j];
            if ( list1.BinarySearch(strNew) <0)
            {
                  list1.Add(strNew);
            }
      }

I expect list1 has object "3", "1", "2", but the result is "3","1","2","3"
the last time when strNew =="3", list1.BinarySearch(strNew) return -4. Normally if
it didn't find the object, it always return -1.

0
jackiechen858
Asked:
jackiechen858
  • 4
  • 3
1 Solution
 
gregoryyoungCommented:
you are missing a ...

"Uses a binary search algorithm to locate a specific element in the sorted ArrayList or a portion of it."

key here is sorted

using System;
using System.Collections ;
namespace ConsoleApplication23
{
      /// <summary>
      /// Summary description for Class1.
      /// </summary>
      class Class1
      {
            /// <summary>
            /// The main entry point for the application.
            /// </summary>
            [STAThread]
            static void Main(string[] args)
            {
                  ArrayList list1 = new ArrayList();
                  list1.Add("3");

                  ArrayList list2 = new ArrayList();
                  list2.Add("1" );
                  list2.Add("2" );
                  list2.Add("3" );
                  
                  int nIdx=list1.BinarySearch("3");

                  for ( int j=0 ; j< list2.Count;j++) {
                        string strNew= (string)list2[j];
                        if ( list1.BinarySearch(strNew) <0) {
                              list1.Add(strNew);
                              list1.Sort();
                        }
                  }
                  Console.WriteLine("list1.Count=" + list1.Count);
                  for(int i=0;i<list1.Count;i++) {
                        Console.WriteLine("List1 [" + i + "] = " + list1[i]);
                  }
            }
      }
}

gives the expected behavior ... you would be better off using a linear search most likely though if you are adding data this frequently (or using a sortedlist instead of an arraylist)
0
 
jackiechen858Author Commented:
Thanks for your quick response Gregory.

I didn't read the document too carefully :-(

0
 
gregoryyoungCommented:
the way binary searches work you need sorted data (are you familiar with the algorithm ?)

basically binary searches use a divide and conquer methodology it tosses out 1/2 of the possible entries everytime it runs (since you are dealing with whole numbers that goes by pretty quickly) ...

http://www.cs.usask.ca/resources/tutorials/csconcepts/1998_3/binary/2-2.html


imagine you have a 1000 page dictionary and someone asks you to find the word "Visual"

open to page 500
first word is "mother"
you flip to page 750 (obviously its not in the first 500 pages)
first word is "testing"
you flip to page 875
the first word is vladamir
you flip to page 813 and find it midway through ...

this is real life example ..

now imagine if after flipping up from mother you found the word "aardvark" ... it would really screw up how you were searching.

0
Cloud Class® Course: Microsoft Exchange Server

The MCTS: Microsoft Exchange Server 2010 certification validates your skills in supporting the maintenance and administration of the Exchange servers in an enterprise environment. Learn everything you need to know with this course.

 
jackiechen858Author Commented:
Yeah, I knew the sort algorithm. I  didn't realize binary search need
sorted data ( should know it but I just didn't think about it too much, maybe
they can  use some magic hash table so no need for sorting:-) ). acturally
I can't use binary search in my code now because I don't want to adjust the
object's sequence in the list. I use the arraylist as a kind of stack.

0
 
gregoryyoungCommented:
why not use the stack object as a stack :)
0
 
jackiechen858Author Commented:
Because  I didn't know there are Stack and Quere object in C# :-(
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now