Are my Java Binary and Linear Search Algorithms working correctly?

Question

Their purpose is to return the number of comparisons between the keys and the array items. Please let me know if there is anything that I should change, as I am new to Java and am not yet fully familiar with best practices.

public class BinaryVsLinear {

private static int linearSearch(int key, int[] array){
  int count = 0;
  for (int i = 0; i < array.length; i++){
      count++;
      if (array[i] == key){
          i += array.length +1;
      }  
  }
  return count;
}

private static int binarySearch(int key, int[] array){

  int count = 0, l = 0, r = array.length -1;
  while (l <= r){
        int m = (l+r)/2;
        count++;
        if (array[m] == key){
            return count;
        }
        count++;
        if (array[m] < key){
            l = m + 1;

        }
        else{
            r = m - 1;
        }
    }
    return count;
}

Is the input to both sorted? Your binary search will only work on sorted data, and the linear search can be sped up if it's working on sorted data (try returning when array[i]>key) — phflack
– phflack, Commented Oct 24, 2017 at 17:17

davidbuzatto · Accepted Answer · 2017-10-24 19:35:07Z

1

Your code is correct, i.e., it counts how many comparisons will be executed both for linear and binary searches. As you is a novice, I would recommend some better practices when writing code, take a look.

public class BinaryVsLinear {

    private static int linearSearch( int key, int[] array ) {

        int count = 0;

        for ( int i = 0; i < array.length; i++ ){
            count++;
            if ( key == array[i] ){
                break;
            }  
        }

        return count;

    }

    private static int binarySearch( int key, int[] array ) {

        // one variable per line
        // use better names
        int count = 0;
        int left = 0;
        int right = array.length -1;

        while ( left <= right ){

            int middle = ( left + right ) / 2;

            count++;
            if ( array[middle] == key ){
                return count;
            }

            count++;
            if ( key > array[middle] ){
                left = middle + 1;
            } else{
                right = middle - 1;
            }

        }

        return count;

    }

}

I added some spaces, change some variable names to better names, etc. It is a matter of preference, but you must always pay attention to the readability of your code.

edited Oct 24, 2017 at 19:35

answered Oct 24, 2017 at 17:24

davidbuzatto

9,4841 gold badge48 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

d.j.brown Over a year ago

Personal preference / company policy will dictate this, but personally I strongly dislike breaks and multiple returns. This article 'Single-entry, single-exit (SESE) heuristic' by Ian Joyner sums up my thoughts on this.

davidbuzatto Over a year ago

@d.j.brown Personal preference / company policy will dictate this yep

Jonah Lang Over a year ago

@d.j.brown how would you recommend the break be changed?

Edwin Buck Over a year ago

I like the better variable names, but I fail to see how this even approaches the question of working correctly. Please update to include something about correctness.

davidbuzatto Over a year ago

@EdwinBuck His code is correct for what it aims to do. I just modify his code to show better practices, since he said that he is new to Java and I am not yet fully familiar with best practices.

|

Collectives™ on Stack Overflow

Are my Java Binary and Linear Search Algorithms working correctly?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related