Geek asks and answers

A timer to see how long the algorithm runs, says my binary search takes longer than a linear search

Here is the class essentially https://gist.github.com/2605302

I tested it several times with different files, and even if there are fewer comparisons for binary search, the time taken is ALWAYS. What's wrong?

public static int linerSearch ( String array [], String word, long resultsArray [])
{
    int comparisons = 0;
    int pos = -1;
    //i have started the timer where the search actualy starts
    long start = System.nanoTime ();
    for (int i = 0; i < array.length; i++){
        comparisons = comparisons + 1;
        if (array [i].equals (word)){
            pos = i;
            break;
        }
    }
    long stop = System.nanoTime ();
    long total = stop - start;
    resultsArray [0] = total;
    resultsArray [1] = (long) (long) array.length;
    resultsArray [2]= (long) (long) comparisons;
    return pos;
}

Here is the following binarySearch class

public  static int binarySearch (String [] array, String word, resultsArray []) {
    int start = 0;
    int end = array.length - 1;;
    int midPt;
    int pos = -1;
    int comparisons2 = 0;
    long start2 = System.nanoTime ();
    Arrays.sort (array);
    while (start <= end) {
        midPt = (start + end) / 2;
        comparisons2 = comparisons2 + 1;
        if (array [midPt].equalsIgnoreCase (word)) {
            pos = midPt;
            break;
        }
        else if (array [midPt].compareToIgnoreCase (word) < 0) {
            start = midPt + 1;
            comparisons2 = comparisons2 + 1;
            //camparisons2 addition was added inside this elseif and other elseif as a work around for not breaking the elseif statement tree, if it has made it two the last elseif then two camparisons after the first one will have been done
        } else if (array [midPt].compareToIgnoreCase (word) > 0)  {
            comparisons2 = comparisons2 + 2;
            end = midPt - 1;
        }
    }
    long stop2 = System.nanoTime ();
    long total2 = stop2 - start2;
    resultsArray [0] = total2;
    resultsArray [1] = (long) (long) array.length;
    resultsArray [2]= (long) (long) comparisons2;
    return pos;
}

edit: I also have to add that I tried it already in a sorted array without this line of code, and that was a long time before it should have been

+3
source share
5 answers

Well, I did it once and for all. First, the binary search method I used here is used:

public static int binarySearch(String[] array, String word, long resultsArray[]) {
    int start = 0;
    int end = array.length - 1;
    int midPt;
    int pos = -1;
    int comparisons2 = 0;

    //Arrays.sort(array);

    long start2 = System.nanoTime();
    while (start <= end) {
        midPt = (start + end) / 2;
        int comparisonResult = array[midPt].compareToIgnoreCase(word);
        comparisons2++;
        if (comparisonResult == 0) {
            pos = midPt;
            break;
        } else if (comparisonResult < 0) {
            start = midPt + 1;
        } else { // comparisonResult > 0
            end = midPt - 1;
        }
    }
    long stop2 = System.nanoTime();
    long total2 = stop2 - start2;

    resultsArray[0] = total2;
    resultsArray[1] = (long) array.length;
    resultsArray[2] = (long) comparisons2;
    return pos;
}

, , .

235882 . , . , . .

, : , Arrays.sort(...) , compareToIgnoreCase , !. , . , Arrays.sort(...) . , compareTo(...) .

,

  • , , compareToIgnoreCase
  • compareTo

: equals equalsIgnoreCase. . :

  • equals: : 725536 ; : 117941; /: 6.15
  • equalsIgnoreCase: : 1064334 ; : 117940; /: 9,02
  • compareToIgnoreCase: : 1619 ; : 16; /: 101.19
  • compareTo: : 763 ; : 16; /: 47,69

, : compareToIgnoreCase 16 , equals!. , 16 , , 124 . , , , , , , - .

, , : 164 compareTo 614 compareToIgnoreCase. 235882 0,3 . , , , .:)

, : binarySearch, . , , . , :

. , , , O (n log n), O (log n), O (n log n). O (n) , , O (n log n). , O (log n) , O (n).

, binarySearch, , 140000000 0,14 . 23000000 equals, , a) b) - .

. , String, , . , , , - , . , ().

+1

, Arrays.sort() , yoy . N . , N .

, , :

1) 1000

2) 1000

+2

:

  • . , ,
  • , equalsIgnoreCase
  • , JIT

, , JDK ( java.util.Arrays).

, . , . .

+1

, . .

0
} else if (array [midPt].compareToIgnoreCase (word) > 0)  {

You do not need this test at all. There is no other option at this point in the code. It is not equal, and it is not less: you have already tested them; therefore it should be bigger.

Thus, you can reduce your comparisons by 33%.

0
source

More articles:


All Articles