Java dichotomy search _ Power node Java College collation

algorithm

If there is a set of 3, 12, 24, 36, 55, 68, 75, 88 to look up the given value 24. Three variables front, mid and end can be set to point to the upper, middle and lower bounds of the data respectively, mid= (front+end) /2.

Start with front=0 (pointing to 3), end=7 (pointing to 88), and mid=3 (pointing to 36). Because mid > x, so look for it in the first half.

Make the new end= ES20en-1 =2 and front=0 unchanged, then the new mid=1. At this point x > mid, so be sure to look it up in the second half.

Make the new front=mid+1=2, and end=2 unchanged, then the new mid=2, then a[mid]=x, the search is successful. If the number you are looking for is not in the sequence, for example x=25, on the third judgment, x > a[mid], according to the above rule, make front=mid+1, that is, front=3, and front appears > About end,

Indicates that the search was unsuccessful.

Example: Look for the user input data x in an ordered array of N elements. The algorithm is as follows:

1. Determine the search scope front=0, end= ES57en-1, and calculate the middle item mid= (front+end) /2.

2. If a[mid]=x or front > =end, then end the search; Otherwise, continue down.

3. If a [mid] < x, indicating that the value of the element to be looked for can only be in a range larger than that of the middle item element, assigns the value of mid+1 to front, recalculates mid, and goes to step 2. If a [mid] > x, indicating that the value of the element to be found can only be smaller than the middle element, assigns the value of mid-1 to end, recalculates mid, and goes to step 2.

Algorithm complexity analysis

Time complexity

1. Find the last element (or first element) in the worst case Master theorem T(n)=T(n/2)+O(1) So T(n)=O(logn)

2. In the best case, find the middle element O(1) find the middle element (the middle of the odd-length sequence and the left of the middle of the even-length sequence)

Space complexity:

S (n) = n

package com.bjpowernode.test;
public class BinarySearch {
  //  Find the number 
  static int count;
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    System.out.println(searchRecursive(array, 0, array.length - 1, 9));
    System.out.println(count);
    count = 0;
    System.out.println(searchLoop(array, 9));
    System.out.println(count);
  }
  /**
   *  Perform recursion 2 Subsearch, return the 1 The position where the value occurs next 
   *
   * @param array
   *       Sorted arrays 
   * @param start
   *       The starting position 
   * @param end
   *       End position 
   * @param findValue
   *       The value you want to find 
   * @return  The position of the value in the array from 0 Start. Unable to find return -1
   */
  public static int searchRecursive(int[] array, int start, int end,
      int findValue) {
    //  If the array is empty, it returns -1 , that is, the search failed 
    if (array == null) {
      return -1;
    }
    count++;
    if (start <= end) {
      //  Middle position 
      int middle = (start + end) / 1;
      //  The median 
      int middleValue = array[middle];
      if (findValue == middleValue) {
        //  Is equal to the median value returned directly 
        return middle;
      } else if (findValue < middleValue) {
        //  If it's less than the median, look before the median 
        return searchRecursive(array, start, middle - 1, findValue);
      } else {
        //  If it's greater than the median, look after the median 
        return searchRecursive(array, middle + 1, end, findValue);
      }
    } else {
      //  return -1 , that is, the search failed 
      return -1;
    }
  }
  /**
   *  cycle 2 Subsearch, return the 1 The position where the value occurs next 
   *
   * @param array
   *       Sorted arrays 
   * @param findValue
   *       The value you want to find 
   * @return  The position of the value in the array from 0 Start. Unable to find return -1
   */
  public static int searchLoop(int[] array, int findValue) {
    //  If the array is empty, it returns -1 , that is, the search failed 
    if (array == null) {
      return -1;
    }
    //  The starting position 
    int start = 0;
    //  End position 
    int end = array.length - 1;
    while (start <= end) {
      count++;
      //  Middle position 
      int middle = (start + end) / 2;
      //  The median 
      int middleValue = array[middle];
      if (findValue == middleValue) {
        //  Is equal to the median value returned directly 
        return middle;
      } else if (findValue < middleValue) {
        //  If it's less than the median, look before the median 
        end = middle - 1;
      } else {
        //  If it's greater than the median, look after the median 
        start = middle + 1;
      }
    }
    //  return -1 , that is, the search failed 
    return -1;
  }
}