Example explanation of Java algorithm on binary search method

This article mainly introduces the relevant information about the detailed explanation of the examples of the binary search method of the Java algorithm. Here is a simple example to help you learn and understand this part of the content. Friends who need it can refer to it

java Detailed explanation of examples of binary search method of algorithm

Principle

Assume that the search range is an ordered array (such as ascending order), from which a certain element is to be found , if the element is in this array, returns its index, otherwise returns -1. The index of the middle element can be taken out through the length of the array, and its value is compared with the target value. If the middle element value is greater than the target value, the search is performed on the left part. If the middle position value is less than the target value, the search is performed on the right part. This cycle continues until the end. The reason why the binary search algorithm is fast is that it does not traverse every element of the array, but only searches for part of the elements to find the target or determine that it does not exist. Of course, the premise is that the search range is an ordered array.

Simple implementation of Java

##

package me.geed.algorithms; 
 
public class BinarySearch { 
 
  /** 
   * 从一个有序数组(如升序)中找到值为key元素 
   * @param key 
   * @param array 
   * @return 如果找到目标元素，则返回其在数组中的索引，否则返回-1 
   */ 
  public static int find(int key, int[] array){ 
    int low = 0; 
    int high = array.length - 1; 
    while (low <= high) { 
      int mid = low + (high - low) / 2; 
      if (array[mid] > key) { 
        high = mid - 1; 
      } else if (array[mid] < key) { 
        low = mid + 1; 
      } else { 
        return mid; 
      }       
    } 
    return -1;    
  } 
   
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] array = {2, 3, 5, 9, 10, 13, 23, 45, 78, 89, 100, 128, 256}; 
    System.out.println("目标元素索引值：" + BinarySearch.find(9, array));     
    System.out.println("目标元素索引值：" + BinarySearch.find(26, array)); 
  } 
 
}

The output result is:

目标元素索引值：3 
目标元素索引值：-1

The time complexity of the binary search algorithm

Assuming that the length of the range array is N, the time complexity of the binary search is O(logN)

The above is the detailed content of Example explanation of Java algorithm on binary search method. For more information, please follow other related articles on the PHP Chinese website!