Cette fois, j'ai essayé d'écrire la tâche d'écrire un programme de recherche par la méthode de la dichotomie avec de jeunes employés. En ce qui concerne la recherche en ligne, il était acceptable sous la restriction que la réponse elle-même ne soit pas vérifiée (copie / copie interdite).
Extrayez toute valeur B par dichotomie du tableau A dans lequel les valeurs numériques de 1 à 1000 sont stockées dans l'ordre.
Comme on suppose que la méthode de la dichotomie sera utilisée cette fois, tout le monde écrira le programme avec la même politique. La procédure de la méthode de la dichotomie est la suivante.
Cependant, il existe quatre façons d'écrire cette phrase par programme, je voudrais donc vous présenter ceci.
Cette fois aussi, ces deux types d'écritures sont sortis les premiers. Veuillez vous référer à la politique de base car elle est la même que l'article précédent.
Une histoire sur la rédaction d'un calcul de ratio lors d'une session d'étude interne
Cependant, puisque cette fois la recherche est à partir d'un tableau, je pense que la limite supérieure du nombre de données dans le tableau n'est pas nécessairement définie lors de son utilisation réelle. Si vous souhaitez l'utiliser dans un projet réel, il est plus sûr d'utiliser une boucle.
Il était également nécessaire de prêter attention au dépassement dû à la méthode de calcul de l'indice évoquée dans le commentaire.
[Wikipedia --Dichotomie - Erreur de mise en œuvre](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2#% E5% AE% 9F% E8% A3% 85% E4% B8% 8A% E3% 81% AE% E9% 96% 93% E9% 81% 95% E3% 81% 84)
J'ai fait une erreur dans le lien ci-dessus, qui a également été publié dans les commentaires. Il y a un risque de débordement si vous ajoutez simplement les index, utilisez donc la soustraction pour éviter le débordement.
Positif
lower + (upper - lower) / 2
Faux
(upper + lower) / 2
Il existe deux façons de procéder à la recherche. Comme c'est difficile à expliquer en lettres, je posterai le code.
Manipulation de tableau.kt
var centerVal: Int = 0
do{
val center: Int = list.size / 2
centerVal = list.get(center)
list = if(centerVal > target) {
list.dropLast(center)
}else {
list.drop(center)
}
}while(centerVal != target)
return centerVal
indice.kt
var centerVal: Int = 0
do{
val center: Int = (start + end) / 2
centerVal = list.get(center)
if(centerVal > target) {
end = center
continue
}
start = center
}while(centerVal != target)
return centerVal
Est-ce comme ça pour chacun? Selon la condition while, il n'est pas nécessaire que ce soit do-while. Il n'y a pas beaucoup de différence d'apparence, et il semble que vous l'aimiez, mais les opérations de tableau sont un traitement lourd et doivent être évitées.
Voici le code qui réécrit ce problème afin qu'il soit facile de comparer ce qui a été écrit dans chaque langue. Comme mentionné ci-dessus, il utilise l'index du tableau et effectue une boucle. Swift est fermé cette fois car il n'y avait pas de participants Swift.
Kotlin
fun main(args: Array<String>) {
val A = List<Int>(1000, { it + 1 })
val B = 233
println(binarySearch(A, B))
}
fun binarySearch(list: List<Int>, target: Int): Int{
if(target < list.first() || list.last() < target) {
return -1
}
var first = 0
var last = list.size
while(first + 1 != last) {
val center = first + (last - first) / 2
val centerVal = list.get(center)
if(centerVal == target) {
return centerVal
}
if(centerVal < target) {
first = center
}else {
last = center
}
}
return -1
}
PHP
<?php
function main() {
$A = range(1, 1000);
$B = 233;
echo binarySearch($A, $B);
}
function binarySearch($list, $target)
{
if ($target < $list[0] || end($list) < $target) {
return -1;
}
$first = 0;
$last = count($list);
while($first + 1 !== $last) {
$center = floor($first + ($last - $first) / 2);
$centerVal = $list[$center];
if($centerVal === $target) {
return $centerVal;
}
if($centerVal < $target) {
$first = $center;
}else {
$last = $center;
}
}
return -1;
}
main();
JavaScript
const main = () => {
const A = new Array(1000)
.fill('a')
.map((el, i) => i + 1)
const B = 233
console.log(binarySearch(A, B))
}
const binarySearch = (list, target) => {
let first = 0
let last = list.length
if(target < list[first] ||list[last-1] < target) {
return -1
}
while (first + 1 !== last) {
const center = Math.floor(first + (last - first) / 2)
const centerVal = list[center]
if (centerVal === target) {
return centerVal
}
if (centerVal < target) {
first = center
} else {
last = center
}
}
return -1
}
main()
Java
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
List<Integer> A = new ArrayList<Integer>() {
{
for(int i = 1; i <= 1000; i++) {
add(i);
}
}
};
int B = 233;
System.out.println(binarySearch(A, B));
}
private static int binarySearch(List<Integer> list, int target) {
int first = 0;
int last = list.size();
if(target < list.get(first) ||list.get(last - 1) < target) {
return -1;
}
while (first + 1 != last) {
final int center = (int) Math.floor(first + (last - first) / 2);
final int centerVal = list.get(center);
if (centerVal == target) {
return centerVal;
}
if (centerVal < target) {
first = center;
} else {
last = center;
}
}
return -1;
}
}
Recommended Posts