Exemple d'explication de l'algorithme Java sur la méthode de recherche binaire

Cet article présente principalement les informations pertinentes sur l'explication détaillée des exemples de la méthode de recherche binaire de l'algorithme Java. Voici un exemple simple pour vous aider à apprendre et à comprendre cette partie du contenu auquel les amis dans le besoin peuvent se référer.

java Explication détaillée d'exemples de méthode de recherche binaire de l'algorithme

Principe

Supposons que la plage de recherche soit ordonnée tableau (comme l'ordre croissant), et vous souhaitez en trouver un certain élément, si l'élément est dans ce tableau, renvoie son index, sinon renvoie -1. L'index de l'élément du milieu peut être extrait sur toute la longueur du tableau et sa valeur est comparée à la valeur cible. Si la valeur de l'élément du milieu est supérieure à la valeur cible, la recherche est effectuée sur la partie gauche. La valeur de la position médiane est inférieure à la valeur cible, la recherche s'effectue sur la partie droite. Ce cycle se poursuit jusqu'à la fin. La raison pour laquelle l'algorithme de recherche binaire est rapide est qu'il ne parcourt pas tous les éléments du tableau, mais recherche uniquement une partie des éléments pour trouver la cible ou déterminer qu'elle n'existe pas. Bien sûr, le principe est que la recherche. range est un tableau ordonné.

Implémentation simple en 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)); 
  } 
 
}

Le résultat de sortie est :

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

Complexité temporelle de l'algorithme de recherche binaire

En supposant que la longueur du tableau de plage est N, alors la complexité temporelle de la recherche binaire est O(logN)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!