Java Community | Help. Code. Learn.•16mo ago

Week 34 — How would one implement a binary search algorithm?

Question of the Week #34

How would one implement a binary search algorithm?

8 Replies

Binary search is an algorithm for finding a specific element in a sorted list or array. It works by first taking a look at the element in the "middle" of the data structure. If the found element is the element in the middle, the position of the element is found immediately. If the element to look for is smaller than the "middle" element, it continues searching through the elements on the left and repeats the procedure. Similarly, in case the element to look for is greater than the element middle element, it continues searching on the right. The advantage of binary search is that it does not need to check each element individually but only a fraction of the elements because it uses the fact that the data structure is sorted. More formally, the algorithm has a runtime complexity of O(log(n)) meaning that for n elements, it only needs logarithm of n instructions ignoring constant factors. With an int[], this can be implemented as follows:

public static int binarySearch(int[] data, int toFind){
  //start by searching through the complete array
  int min = 0;//start index of the part to search
  int max = data.length;//end index of the part to search
  while(min<max) {//still something left to search
    int middle = (min+max)/2;//find element in the middle between min and max
    if(toFind < data[middle]){
      max = middle;//the next time, we only need to search from min to middle
    } else if (toFind > data[middle]) {
      min = middle+1;//the next time, we only need to search from middle to max but not include middle in the search any more
    } else {//element found
      return middle;//return the index of the found element
    }
  }
  return -1;//return -1 to indicate that the element has not been found
}

public static int binarySearch(int[] data, int toFind){
  //start by searching through the complete array
  int min = 0;//start index of the part to search
  int max = data.length;//end index of the part to search
  while(min<max) {//still something left to search
    int middle = (min+max)/2;//find element in the middle between min and max
    if(toFind < data[middle]){
      max = middle;//the next time, we only need to search from min to middle
    } else if (toFind > data[middle]) {
      min = middle+1;//the next time, we only need to search from middle to max but not include middle in the search any more
    } else {//element found
      return middle;//return the index of the found element
    }
  }
  return -1;//return -1 to indicate that the element has not been found
}

If we want to search through a list of arbitrary objects, we need a way to compary two objects i.e. whether they are considered equal or which one of them is smaller/bigger. For that, we use the Comparator interface which provides the method compare. comparator.compare(a,b) returns a value >0 iff a is greater than b, <0 iff a is smaller than b and 0 if they should be considered equal:

public static <T> int binarySearch(List<T> data, T toFind, Comparator<T> comparator){
  //start by searching through the complete array
  int min = 0;//start index of the part to search
  int max = data.size();//end index of the part to search
  while(min<max) {//still something left to search
    int middle = (min+max)/2;//find element in the middle between min and max
    int comparatorResult = comparator.compare(toFind, data.get(middle));
    if(comparatorResult < 0){
      max = middle;//the next time, we only need to search from min to middle
    } else if (comparatorResult > 0) {
      min = middle+1;//the next time, we only need to search from middle to max but not include middle in the search any more
    } else {//element found
      return middle;//return the index of the found element
    }
  }
  return -1;//return -1 to indicate that the element has not been found
}

public static <T> int binarySearch(List<T> data, T toFind, Comparator<T> comparator){
  //start by searching through the complete array
  int min = 0;//start index of the part to search
  int max = data.size();//end index of the part to search
  while(min<max) {//still something left to search
    int middle = (min+max)/2;//find element in the middle between min and max
    int comparatorResult = comparator.compare(toFind, data.get(middle));
    if(comparatorResult < 0){
      max = middle;//the next time, we only need to search from min to middle
    } else if (comparatorResult > 0) {
      min = middle+1;//the next time, we only need to search from middle to max but not include middle in the search any more
    } else {//element found
      return middle;//return the index of the found element
    }
  }
  return -1;//return -1 to indicate that the element has not been found
}

Eric McIntyre•16mo ago

Since sorting is a fundamental operation used by many programs, Java actually provides methods like this to search through sorted arrays and lists. For applying a binary search on a sorting array, one can use Arrays.binarySearch, e.g. Arrays.binarySearch(new int[]{1,2,3,4,5,6},5). In order to use a binary search for a list of elements, one can use the Collections.binarySearch method which is provided by Java as well, e.g. Collections.binarySearch(List.of("a","b","c","d","e"),"d",Comparator.naturalOrder()). Note that these methods don't always return -1 if the element was not found but actually a negative value that also represents the position where the element would need to be inserted.

⭐ Submission from dan1st#0000

Eric McIntyre•16mo ago

public class BinarySearch {

    public static void main(String[] args){
        //Test
        int[] ints = new int[]{
                1, 2, 5, 7, 8, 23, 25, 37, 39, 40, 42, 56, 78, 88, 89, 96, 105, 286, 354, 456, 467, 489, 566, 667, 892, 1002, 1003, 1005, 1234, 1260
        };
        System.out.println(binarySearch(ints, 354));
    }

    /**
     * Binary search only works on sorted arrays.
     *
     * @param sortedArray an array of sorted integers from smallest to biggest.
     * @param target the target value trying to find.
     * @return Returns null if target is not found. If found, returns the index.
     * **/
    @Nullable
    public static Integer binarySearch(int[] sortedArray, int target){
        int low = 0;
        int high = sortedArray.length;
        int mid = getMid(high, low);
        while(high > low){
            if(target < sortedArray[mid]){
                high = mid;
                mid = getMid(high, low);
            }else if (target > sortedArray[mid]){
                low = mid;
                mid = getMid(high, low);
            }else{
                return mid;
            }
        }
        return null;
    }

    private static int getMid(int high, int low){
        return Math.round((float) ((high - low) / 2) + low);
    }

}

public class BinarySearch {

    public static void main(String[] args){
        //Test
        int[] ints = new int[]{
                1, 2, 5, 7, 8, 23, 25, 37, 39, 40, 42, 56, 78, 88, 89, 96, 105, 286, 354, 456, 467, 489, 566, 667, 892, 1002, 1003, 1005, 1234, 1260
        };
        System.out.println(binarySearch(ints, 354));
    }

    /**
     * Binary search only works on sorted arrays.
     *
     * @param sortedArray an array of sorted integers from smallest to biggest.
     * @param target the target value trying to find.
     * @return Returns null if target is not found. If found, returns the index.
     * **/
    @Nullable
    public static Integer binarySearch(int[] sortedArray, int target){
        int low = 0;
        int high = sortedArray.length;
        int mid = getMid(high, low);
        while(high > low){
            if(target < sortedArray[mid]){
                high = mid;
                mid = getMid(high, low);
            }else if (target > sortedArray[mid]){
                low = mid;
                mid = getMid(high, low);
            }else{
                return mid;
            }
        }
        return null;
    }

    private static int getMid(int high, int low){
        return Math.round((float) ((high - low) / 2) + low);
    }

}

Eric McIntyre•16mo ago

Binary search is a very powerful algorithm, as it allows search in O(log n) time complexity. However the down side is that you need a sorted array, and sorting the array may require more computational resources, but with efficient sorting algorithms like quick sort, binary search is still a good choice.

Submission from friskaunderscore#0000

Eric McIntyre•16mo ago

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Eric McIntyre•16mo ago

What do i get for answear?

Submission from kazaruma#0000

Eric McIntyre•16mo ago

A binary search is a type of search algorithm that is optimized to work well with comparable elements in a sorted set. The set being sorted allows it to easily figure out which elements are where, since you can compare the element to be searched with the current element being looked at, and figure out of the element being searched should be at a lower index or at a higher index. The first step of a binary search is to compare the searched element with the middle element. If the searched element is smaller than the middle element, you can figure out that the searched element must be in the lower half of the list, since the list is sorted. If not, the element has to be in the upper half. Then, the algorithm visits the middle of the new region and compares that with the searched element, and from there on out you just repeat. An example on how that would work for a set of integers:

Initial: [1, 3, 5, 6, 9, 11, 12], searching for 5

First:             V bigger than 5, lower half
         [1, 3, 5, 6, 9, 11, 12]

Second:      V smaller than 5, upper half
         [1, 3, 5, 6, 9, 11, 12]

Third:          V exactly 5, index 2
         [1, 3, 5, 6, 9, 11, 12]

Initial: [1, 3, 5, 6, 9, 11, 12], searching for 5

First:             V bigger than 5, lower half
         [1, 3, 5, 6, 9, 11, 12]

Second:      V smaller than 5, upper half
         [1, 3, 5, 6, 9, 11, 12]

Third:          V exactly 5, index 2
         [1, 3, 5, 6, 9, 11, 12]

Of course you need to keep track of your current position in the list, an easy way to figure that out is to store the current region's start index and length. For the first iteration in the example, the index would be 0 and the length would be the entire length of the list, 7. For the second+ iteration, the index would be either the start index of the previous iteration, or the start index + (length - 1) / 2 + 1, depending on if you branched left or right. The length would be (previousLength - 1) / 2. This continues onward for every next iteration.

First: Index 0 length 7
Second: Index 0 length (7 - 1) / 2 = 3
Third: Index 0 + (3-1)/2 + 1 = 2, length (3 - 1) / 2 = 1

First: Index 0 length 7
Second: Index 0 length (7 - 1) / 2 = 3
Third: Index 0 + (3-1)/2 + 1 = 2, length (3 - 1) / 2 = 1

Eric McIntyre•16mo ago

A general java implementation should look something like this:

<T extends Comparable<T>> int binarySearch(T[] ts, T search) {
    int currentStart = 0, currentLength = ts.length;
    while (true) {
        if (currentLength == 1) {
            T midP = ts[currentStart];
            if (search.compareTo(midP) != 0) return -1; // the only element isn't it
            return currentStart; // this is it
        }
        int midIndex = currentStart + currentLength / 2;
        if (currentLength % 2 == 0) midIndex--;
        T midPoint = ts[midIndex];
        int compareToRes = search.compareTo(midPoint);
        if (compareToRes == 0) return midIndex;
        if (compareToRes > 0) {
            currentStart = currentStart + (currentLength - 1) / 2 + 1;
        }
        currentLength = (currentLength - 1) / 2;
    }
}

<T extends Comparable<T>> int binarySearch(T[] ts, T search) {
    int currentStart = 0, currentLength = ts.length;
    while (true) {
        if (currentLength == 1) {
            T midP = ts[currentStart];
            if (search.compareTo(midP) != 0) return -1; // the only element isn't it
            return currentStart; // this is it
        }
        int midIndex = currentStart + currentLength / 2;
        if (currentLength % 2 == 0) midIndex--;
        T midPoint = ts[midIndex];
        int compareToRes = search.compareTo(midPoint);
        if (compareToRes == 0) return midIndex;
        if (compareToRes > 0) {
            currentStart = currentStart + (currentLength - 1) / 2 + 1;
        }
        currentLength = (currentLength - 1) / 2;
    }
}

⭐ Submission from 0x150#0000

Gaming

Programming

Week 34 — How would one implement a binary search algorithm?