Solved

Why BinarySearch return a wrong value ? ( -4)

Posted on 2004-08-31
7
273 Views
Last Modified: 2010-04-15
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
Comment
Question by:jackiechen858
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
7 Comments
 
LVL 37

Accepted Solution

by:
gregoryyoung earned 100 total points
ID: 11946601
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
 
LVL 7

Author Comment

by:jackiechen858
ID: 11946711
Thanks for your quick response Gregory.

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

0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 11946840
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
PeopleSoft Has Never Been Easier

PeopleSoft Adoption Made Smooth & Simple!

On-The-Job Training Is made Intuitive & Easy With WalkMe's On-Screen Guidance Tool.  Claim Your Free WalkMe Account Now

 
LVL 7

Author Comment

by:jackiechen858
ID: 11947190
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
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 11947270
why not use the stack object as a stack :)
0
 
LVL 7

Author Comment

by:jackiechen858
ID: 11952577
Because  I didn't know there are Stack and Quere object in C# :-(
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 11953117
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction Although it is an old technology, serial ports are still being used by many hardware manufacturers. If you develop applications in C#, Microsoft .NET framework has SerialPort class to communicate with the serial ports.  I needed to…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This video…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

733 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question