Binary Search

Searching

Binary Search

🙋 Need help? Ask an expert now!

As we discussed previously, sequential search can take an excessively long time since they look through every element in an array. This is like flipping through each page of the dictionary from the beginning even if we are trying to find the word "zero". Let's introduce the concept of binary search, which is similar to flipping right to the 'Z' section of the dictionary to start looking for the word "zero". If an array or ArrayList is ordered, the binary search method can be used. Look below and review the functionality of a binary search.

BinarySearchExample.java
package exlcode;

public class BinarySearchExample {

  public static void main(String[] args) {
    // the array has to be sorted before binary search
    int[] exampleVariableOne = {1, 11, 24, 34, 67, 89, 102};
    int target = 102;
    binarySearch(exampleVariableOne, target);
  }

  public static void binarySearch(int[] parameterOne, int parameterTwo) {
    int index = -1;
    int lowEnd = 0;
    int highEnd = parameterOne.length - 1;
    while (highEnd >= lowEnd) { // Difference of highEnd and lowEnd decreases as the search range narrows
      int middle = (lowEnd + highEnd) / 2;
      // checks if the middle of the lowEnd and the highEnd is the target
      if (parameterOne[middle] == parameterTwo) {
        index = middle; // the target is found
        break;
      } else if (parameterOne[middle] < parameterTwo) {
        // changes the lowEnd to narrow the search range
        lowEnd = middle + 1;
      } else if (parameterOne[middle] > parameterTwo) {
        // changes the highEnd to narrow the search range
        highEnd = middle - 1;
      }
    }
    if (index == -1) {
      System.out.println("Your target integer does not exist in the array");
    } else {
      System.out.println("Your target integer is in index " + index + " of the array");
    }
  }
}

Again, a binary search will only work if we have a sorted list. Duplicate values don't affect the search. A binary search starts at the middle of a sorted list and assess if the value it's called to look for is greater than of less than the middle. This initial procedure establishes whether the target value is in the first or second half of the list, at which point the search changes its high and low values to focus on the correct half of the list. Then, the search enters the middle of its chosen half and does the exact same procedure over and over again until the target value is found.

Although you will not need to know how to write your own search methods, you do have to understand what a search method does and how it works in order to use them effectively.

Edit Me on GitHub!

Application Question

Given an array, which of the following condition must be true in order to search for a value using binary search?

I. The values in the array must be integers.
II. The values in the array must be in sorted order.
III. The array cannot contain duplicate values.