Binary search in Java

Question

I have started learning Java recently and was looking into some easy algorithms. I found the Binary Search Algorithm here

I am trying to get better at writing good code for my solutions. I have used MergeSort for sorting the unsorted array first.Please give me your suggestions.

 import java.util.Scanner;
 public class binarysearch {
 public static void main(String[] args) {
 Scanner keyboard = new Scanner(System.in);
 int size = keyboard.nextInt();
 int[] array = new int[size];
 for (int i = 0; i < array.length; i++) {
 array[i] = keyboard.nextInt();
 }
 // sort the array using mergesort
 mergeSort (array);
 System.out.println("Enter the element to search");
 int searchkey = keyboard.nextInt();
 // call the function to do the binary search
 binarySearch (array, searchkey);
 }
 private static void binarySearch(int[] array, int searchkey) {
 int low = 0; // lowest index
 int high = array.length - 1; // highest index
 int guess = (low + high) / 2;
 while (low <= high) {
 if (array[guess] == searchkey) {
 System.out.println("The element " + searchkey
 + " is found at the index " + guess);
 break;
 } else if (array[guess] < searchkey) {
 low = guess + 1;
 } else
 high = guess - 1;
 guess = (low + high) / 2;
 }
 if (low > high) {
 System.out.println("The element " + searchkey + " is not found");
 }
 }
 private static int[] mergeSort(int[] a) {
 if (a.length <= 1) {
 return a;
 }
 // split the array into two halves
 int[] first = new int[a.length / 2];
 int[] second = new int[a.length - first.length];
 System.arraycopy(a, 0, first, 0, first.length);
 System.arraycopy(a, first.length, second, 0, second.length);
 mergeSort (first);
 mergeSort (second);
 merge (first, second, a);
 return a;
 }
 private static void merge(int[] first, int[] second, int[] a) {
 int i = 0;
 int j = 0;
 int k = 0;
 while (i < first.length && j < second.length) {
 if (first[i] <= second[j]) {
 a[k] = first[i]; 
 i++;
 k++;
 } else {
 a[k] = second[j]; 
 j++;
 k++;
 }
 }
 while (i < first.length) {
 a[k++] = first[i++];
 }
 while (j < second.length) {
 a[k++] = second[j++];
 }
 }
 }

Answer 1

I'll only be reviewing the binary search portion of the code since that's what it seems like you're asking for.

Separation of Concerns

You should separate I/O from processing and let the user control what kind of I/O they'd like to have. So I would remove the output statements from your binarySearch function and find a better way to indicate the element was not found. The solution I'll go with is that we'll return the index of the element if it is found and -1 otherwise (since -1 is never a valid array index).

Better Naming

You call the middle element guess even though it is not a guess. Someone unfamiliar with binary search would read this code and assume that you guessed the element was in the middle. This is not true so I would rename that variable to pivot or middle. Moreover, you can move the calculation of it to be inside the while loop.

Miscellaneous

1. Use consistent bracing style (e.g. always use them. They never hurt).
2. The if statement at the end of the binary search is unnecessary since when we exit the while loop, we know that low > high.
3. Since middle won't be changing in one while loop cycle, we can mark it final.

Here is a possible implementation taking into account all of the above.

 private static int binarySearch(int[] array, int searchkey) {
 int low = 0; // lowest index
 int high = array.length - 1; // highest index
 while (low <= high) {
 final int middle = low + (high - low) / 2;
 if (array[middle] == searchkey) {
 return middle;
 } else if (array[middle] < searchkey) {
 low = middle + 1;
 } else {
 high = middle - 1;
 }
 }
 return -1;
 }