Java implémente la recherche binaire

Qu'est-ce que la recherche binaire :

La recherche biométrique est également une recherche binaire, recherchant l'élément spécifié dans une séquence ordonnée, définissant l'indice minimum (faible) et le index maximum (hauteur-1) et la valeur intermédiaire mid ((low+height-1)/2), pour cette recherche, si la valeur intermédiaire est plus petite que l'élément spécifié, soit low=mid+1, si la valeur intermédiaire est plus grand que l'élément spécifié, Soit height=mid-1;

Implémentation du code : (Partage gratuit du didacticiel vidéo : Tutoriel vidéo Java)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
				int arr[] = { 2, 5, 6, 8, 9, 4, 7 };
				Arrays.sort(arr);
				int deix（索引） = getxiabiao(arr, 7);
				
			}
			public static int getxiabiao(int[] arr, int key) {
				int heigh = arr.length-1;
				int low = 0;
				int mid = 0;
				while (low <= heigh) {
					mid = low + (heigh - low)/2;
					if (arr[mid] == key) {
						return mid;
					} else if (arr[mid] < key) {
						low = mid + 1;
					} else if (arr[mid] > key) {
						heigh = mid - 1;
					}
				}
				return -1;
			}
		}

Il existe deux manières pour définir la valeur intermédiaire;

Algorithme 1 : mid = (bas + haut) / 2

Algorithme 2 : mid = bas + (haut – bas)/2

A première vue, l'algorithme 1 est simple, après extraction par l'algorithme 2, il n'y a aucune différence avec l'algorithme 1. Mais en fait, la différence existe.

L'approche de l'algorithme 1, dans les cas extrêmes, il existe un risque de débordement de (bas + haut), ce qui conduira à des résultats moyens erronés, conduisant à des erreurs de programme. Cependant, l'algorithme 2 peut garantir que le Le milieu calculé doit être supérieur au bas, plus petit que haut, il n'y a pas de problème de débordement.

Articles et tutoriels connexes recommandés : Tutoriel d'introduction à Java

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!