Introduction to the

Binary Search, also known as Binary Search, is a highly efficient Search method. However, the split search requires that the linear table must have a sequential storage structure and that the elements in the table are arranged in keyword order

Thought analysis

  1. First determine the middle subscript of the array mid = (left + right) / 2

  2. Then compare the number you want to find, findVal, to arr[mid]

    • FindVal > arr[mid]; findVal > arr[mid]; findVal > arr[mid]
    • FindVal < arr[mid] means that the number you are looking for is to the left of mid, so you need to recursively search to the left
    • FindVal == arr[mid

  3. When we need to end the recursion.

    • The recursion ends when we find it
    • If we recurse the entire array, and we still haven’t found findVal, we need to end the recursion and when left > right we need to exit

Code implementation

package com.company;
// Note: Binary search is used only if the array is ordered.
public class BinarySearch {
  public static void main(String[] args) {
    int arr[] = {1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20};
    int index = binarySearch(arr, 0, arr.length - 1.8);
    System.out.println("index=" + index);
  }
  // Binary search algorithm

  / * * *@paramArray arr *@paramLeft Index * to the left@paramIndex * on the right@paramThe value * that findVal is looking for@returnReturn the index if found, or -1 */ if not found
  public static int binarySearch(int[] arr, int left, int right, int findVal) {
    // When left > right, the entire array is recursed, but not found
    if (left > right) {
      return -1;
    }
    int mid = (left + right) / 2;
    int midVal = arr[mid];
    if (findVal > midVal) { // Recurse to the right
      return binarySearch(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) { // Recurse to the left
      return binarySearch(arr, left, mid - 1, findVal);
    } else {
      returnmid; }}}Copy the code

When there are multiple iterations worth

  • For example {1,8, 10, 89, 1000, 1000, 1234} when an ordered array,
  • When you have multiple values of the same value, how do you find all of them, like 1000 here
    • Thought analysis
      1. Do not return the mid index immediately after it is found
      1. Scan to the left of the mid index and add the subscripts of all elements that satisfy 1000 to the collection ArrayList
      1. Scan to the right of the mid index and add the subscripts of all elements that satisfy 1000 to the collection ArrayList
      1. The Arraylist return
package com.company;

import java.util.ArrayList;
import java.util.List;

// Note: Binary search is used only if the array is ordered.
public class BinarySearch {
  public static void main(String[] args) {
    int arr[] = {1.8.10.89.1000.1000.1234};
    List<Integer> integers = binarySearch2(arr, 0, arr.length - 1.1000);
    System.out.println(integers);
  }

  public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
    // When left > right, the entire array is recursed, but not found
    if (left > right) {
      return new ArrayList<Integer>();
    }
    int mid = (left + right) / 2;
    int midVal = arr[mid];

    if (findVal > midVal) { // Recurse to the right
      return binarySearch2(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) { // Recurse to the left
      return binarySearch2(arr, left, mid - 1, findVal);
    } else {
      List<Integer> resIndexlist = new ArrayList<Integer>();
      // Scan the left side of the mid index and add the subscripts of all elements that satisfy 1000 to the ArrayList
      int temp = mid - 1;
      while (true) {
        if (temp < 0|| arr[temp] ! = findVal) {/ / exit
          break;
        }
        // Otherwise, put temp into resIndexlist
        resIndexlist.add(temp);
        temp -= 1; / / temp shift to the left
      }
      resIndexlist.add(mid);

      // Scan to the right of the mid index and add the subscripts of all elements that satisfy 1000 to the ArrayList
      temp = mid + 1;
      while (true) {
        if (temp > arr.length - 1|| arr[temp] ! = findVal) {/ / exit
          break;
        }
        // Otherwise, put temp into resIndexlist
        resIndexlist.add(temp);
        temp += 1; / / temp moves to the right
      }
      returnresIndexlist; }}}Copy the code