Java code example to implement binary search

This article mainly introduces relevant information about Java binary search. Friends who need it can refer to it

Algorithm

If there is one The number of groups is 3, 12, 24, 36, 55, 68, 75, 88. To check the given value 24. You can set three variables front, mid, end to point to respectively The upper, middle and lower bounds of the data, mid=(front+end)/2.

Start with front=0 (pointing to 3), end=7 (pointing to 88), then mid=3 (pointing to 36) ). Because mid>x, it should be searched in the first half of the paragraph.

Let the new end=mid-1=2, and front=0 remain unchanged, then the new mid=1. At this time, x>mid, so it must be searched in the second half.

Let the new front=mid+1=2, and end=2 remain unchanged, then the new mid=2, at this time a[mid]=x, the search is successful. If the number to be searched is not a number in the sequence, for example, x=25, when the third judgment is made, x>a[mid], according to the above rules, let front=mid+1, that is, front=3, and front>end appears In the case of ,

means the search was unsuccessful.

Example: Find the data x entered by the user in an ordered array with N elements. The algorithm is as follows:

1. Determine the search range front=0, end=N-1, and calculate the middle term mid=(front+end)/2.

2. If a[mid]=x or front>=end, end the search; otherwise, continue downward.

3. If a[mid]x, it means that the value of the element to be found can only be in a smaller range than the middle element, then assign the value of mid-1 to end, and recalculate mid, Go to step 2.

Algorithm complexity analysis

Time complexity

　1. Worst Situation Find the last element (or first element) Master's theorem T(n)=T(n/2)+O(1) so T(n)=O(logn)

　2. Best In case of finding the middle element O(1), the element searched is the middle element (the middle element of the odd-length sequence, the middle left element of the even-length sequence)

Space complexity:

S(n)=n

package com.bjpowernode.test;
public class BinarySearch {
  // 查找次数
  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);
  }
  /**
   * 执行递归二分查找，返回第一次出现该值的位置
   *
   * @param array
   *      已排序的数组
   * @param start
   *      开始位置
   * @param end
   *      结束位置
   * @param findValue
   *      需要找的值
   * @return 值在数组中的位置，从0开始。找不到返回-1
   */
  public static int searchRecursive(int[] array, int start, int end,
      int findValue) {
    // 如果数组为空，直接返回-1，即查找失败
    if (array == null) {
      return -1;
    }
    count++;
    if (start <= end) {
      // 中间位置
      int middle = (start + end) / 1;
      // 中值
      int middleValue = array[middle];
      if (findValue == middleValue) {
        // 等于中值直接返回
        return middle;
      } else if (findValue < middleValue) {
        // 小于中值时在中值前面找
        return searchRecursive(array, start, middle - 1, findValue);
      } else {
        // 大于中值在中值后面找
        return searchRecursive(array, middle + 1, end, findValue);
      }
    } else {
      // 返回-1，即查找失败
      return -1;
    }
  }
  /**
   * 循环二分查找，返回第一次出现该值的位置
   *
   * @param array
   *      已排序的数组
   * @param findValue
   *      需要找的值
   * @return 值在数组中的位置，从0开始。找不到返回-1
   */
  public static int searchLoop(int[] array, int findValue) {
    // 如果数组为空，直接返回-1，即查找失败
    if (array == null) {
      return -1;
    }
    // 起始位置
    int start = 0;
    // 结束位置
    int end = array.length - 1;
    while (start <= end) {
      count++;
      // 中间位置
      int middle = (start + end) / 2;
      // 中值
      int middleValue = array[middle];
      if (findValue == middleValue) {
        // 等于中值直接返回
        return middle;
      } else if (findValue < middleValue) {
        // 小于中值时在中值前面找
        end = middle - 1;
      } else {
        // 大于中值在中值后面找
        start = middle + 1;
      }
    }
    // 返回-1，即查找失败
    return -1;
  }
}

The above is the detailed content of Java code example to implement binary search. For more information, please follow other related articles on the PHP Chinese website!