1

Possible Duplicate:
What is the difference between Linear search and Binary search?

Write a program that generates 20 random integers within the range from 0 to 100. Sort the array in descending order. Then, accepts an integer input from the user. Then, search the array using this number. Compare the performance of linear search and binary search.

Here is my code

import java.util.Arrays;    
import java.util.Scanner;

public class search {

    public static void main(String args[]) {
        int[] num = new int[20];
        for (int i = 0; i < num.length; i++) {

            num[i] = (int) (Math.random() * 101);
        }
        System.out.println("A list of 20 random intergers with 0 - 100");
        System.out.println(Arrays.toString(num));
        for (int j = 1; j < num.length; j++) {
            for (int k = 0; k < num.length - 1; k++) {
                if (num[k] < num[k + 1]) {
                    int hold = num[k + 1];
                    num[k + 1] = num[k];
                    num[k] = hold;
                }
            }

        }
        System.out.println("Array in descending order");
        System.out.println(Arrays.toString(num));
        Scanner input = new Scanner(System.in);
        System.out.print("Enter a number to search: ");
        int num2 = input.nextInt();
        int loop = 0;
        for ( int cnt = 0; cnt < num.length; cnt++ )
        {
            if ( num[cnt] == num2 )
            {
                loop = cnt;
                System.out.println(num2+ " found"); 
          }

        }
        System.out.println("Linear search - "+loop+ " loop(s)");
        int loop2 = 0;
        int low = 0;   // low element subscript
        int high = num.length - 1;  // high element subscript
        int middle;    // middle element subscript
        while ( low <= high ) {
            middle = ( low + high ) / 2;
            if ( num2 == num[ middle ] ) { 

            }
            else if ( num2 > num[ middle ] )
            {
              low = middle +1;
               loop2++;
            }
            else{
              high = middle - 1;   
               loop2++;
            }                      
      }
        System.out.println("Binary search - "+loop2+ " loop(s)");
    }
}

I can get number of loop of Linear search. However, I can't get binary search loops number.

Community
  • 1
  • 1
user1761325
  • 93
  • 2
  • 9
  • 2
    What do you mean you "can't get it"? Do you have an error or something? – alestanis Oct 21 '12 at 10:17
  • `Compare the performance of linear search and binary search` might also mean the number of comparisons performed rather than counting the number of loops. – Sujay Oct 21 '12 at 10:18
  • what is the output of `System.out.println("Binary search - "+loop2+ " loop(s)");`? – mcalex Oct 21 '12 at 10:20
  • 1
    Might I suggest that you `break` out of your search if you find the element you're looking for. If you don't, you will always get worst case for both searches. – Michael Oct 21 '12 at 10:22

2 Answers2

3

Your binary search is missing a break in:

        if ( num2 == num[ middle ] ) { 

        }

Also your binary search is for ascending order but you actually have a descending order! Either reverse your sort or adjust your search algorithm.

Eelke
  • 20,897
  • 4
  • 50
  • 76
0

I suggest to use the comparison-count in place of loop-count as it reflects more the cost of the algorithms. You can easily count the comparisons. In this particular case though, the two happen to be equivalent.

int comparisons = 0;
while ( low <= high ) {
   middle = ( low + high ) / 2;
   ++comparisons;
   if ( num2 > num[ middle ] ) {
      low = middle +1;
   }
   else if ( num2 < num[ middle ] ) {
      high = middle - 1;   
   }
   else {
      break;
   }               
}
System.out.println( "Binary search - " + comprisons + " loop(s)");
rrufai
  • 1,475
  • 14
  • 26
Aubin
  • 14,617
  • 9
  • 61
  • 84
  • Downvoting. If you want to count comparisons, you should count both branches of the if statement. Counting one half isn't enough. Even the case for equality is also a comparison. So, loop counting is the right thing to do. – rrufai Oct 21 '12 at 10:56
  • You're right, sorry. I have edited the source. – Aubin Oct 21 '12 at 12:33
  • I removed the downvote. You can still reduce the number of comparisons made by your code though, if you combine all three comparisons into one if-else-if-else structure. Right now you're always doing the equality check in every iteration. I've edited your code reflect this, if it's not ok with you, feel free to revert. – rrufai Oct 21 '12 at 17:25