Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Binary Search algorithm in Java

farenda 2016-07-18 0

Binary Search algorithm in Java

Binary Search is the fastest algorithm for finding an element in a sorted list. Also it’s easy to implement what we’re going to show in this post.

How it works

The procedure is simple:

  1. Take element from the center and compare with expected value.
  2. If found return its index.
  3. If expected value is bigger, repeat from step 1, but only for part of array from the second half. Because the array is sorted we know that everything from the first half is smaller than the target element, so no need to compare.
  4. If expected value is lower, repeat from step 1, but only for part of array from the first half.
  5. Return some value that indicates that the expected value was not found (usually -1) or negative index – 1 of place where it can be inserted, to simplify insertion for users (optional, but easy to do).

Binary Search properties

  • input array must be sorted
  • computational complexity in the worst case is O(log n + 1) (not found), best is O(1) (hit on the first guess)
  • returns index of target element when found
  • returns negative index minus one of insertion point of target element, in case when was not found

Binary Search implementation

In this implementation we are working with integers, but it can be easily changes to work with any Java objects that are comparable (or by providing custom Comparator):

package com.farenda.tutorials.algorithms.searching;

public class BinarySearch {

    public static int find(int[] numbers, int target) {
        int min = 0, max = numbers.length-1;

        while (min <= max) {
            int pos = (min+max) / 2;
            if (numbers[pos] == target) {
                return pos;
            }
            if (numbers[pos] < target) {
                min = pos + 1;
            } else {
                max = pos - 1;
            }
        }

        // +1, because 0 belongs to positive indices
        return -(min+1);
    }
}

Unit testing

Let’s write some JUnit tests to verify our implementation. We can use Fibonacci numbers as our sorted array of numbers:

package com.farenda.tutorials.algorithms.searching;

import java.util.Arrays;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class BinarySearchTest {

    private static final int[] FIBOS
            = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 };

    // Tests will go here:
}

JUnit test to check that numbers are found correctly

@Test
public void shouldFindIndexOfNumber() {
    // Our version:
    assertEquals(3, BinarySearch.find(FIBOS, 3));
    assertEquals(9, BinarySearch.find(FIBOS, 55));

    // JDK version:
    assertEquals(3, Arrays.binarySearch(FIBOS, 3));
    assertEquals(9, Arrays.binarySearch(FIBOS, 55));
}

Here we’ve added calls for Binary Search method from java.util.Arrays just to compare the results.

JUnit test to check insertion point

In the case when expected number is not found it’s easy to a return pointer to a place where it can be inserted. Here we’re going to verify that it works:

@Test
public void shouldReturnNegativeInsertionPointWhenNotFound() {
    // Our version:
    assertEquals(-1, BinarySearch.find(FIBOS, 0));
    assertEquals(-5, BinarySearch.find(FIBOS, 4));

    // JDK version:
    assertEquals(-1, Arrays.binarySearch(FIBOS, 0));
    assertEquals(-5, Arrays.binarySearch(FIBOS, 4));
}

References:

  • JUnit Tutorial
  • Java BinarySearch with custom Comparator
Share with the World!
Categories Algorithms Tags algorithms, java
Previous: Java Util Optional.ofNullable(T)
Next: Java Util Optional map(Function)

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2022

sponsored