Dieses Mal habe ich versucht, zusammen mit jungen Mitarbeitern die Aufgabe zu schreiben, ein Suchprogramm nach der Dichotomiemethode zu schreiben. In Bezug auf die Online-Suche war es in Ordnung, unter der Einschränkung, dass die Antwort selbst nicht überprüft wird (Kopieren / Kopieren verboten).
Extrahieren Sie einen beliebigen Wert B durch Dichotomie aus Array A, in dem numerische Werte von 1 bis 1000 der Reihe nach gespeichert sind.
Da davon ausgegangen wird, dass diesmal die Dichotomiemethode verwendet wird, schreibt jeder das Programm mit derselben Richtlinie. Das Verfahren der Dichotomie-Methode ist wie folgt.
Es gibt jedoch vier Möglichkeiten, diesen Satz programmgesteuert zu schreiben, daher möchte ich dies einführen.
Auch diesmal kamen diese beiden Arten des Schreibens zuerst heraus. Bitte beachten Sie die grundlegenden Richtlinien, da diese mit denen des vorherigen Artikels identisch sind.
Eine Geschichte über das Schreiben einer Verhältnisberechnung bei einer internen Studiensitzung
Da die Suche diesmal jedoch von einem Array aus erfolgt, denke ich, dass die Obergrenze für die Anzahl der Daten im Array nicht unbedingt festgelegt ist, wenn es tatsächlich verwendet wird. Wenn Sie es in einem realen Projekt verwenden möchten, ist es sicherer, eine Schleife zu verwenden.
Aufgrund der im Kommentar genannten Indexberechnungsmethode musste auch auf den Überlauf geachtet werden.
[Wikipedia - Dichotomie - Implementierungsfehler](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)
Ich habe einen Fehler im obigen Link gemacht, der auch in den Kommentaren gepostet wurde. Wenn Sie einfach die Indizes hinzufügen, besteht die Gefahr eines Überlaufs. Verwenden Sie daher die Subtraktion, um einen Überlauf zu vermeiden.
Positiv
lower + (upper - lower) / 2
Falsch
(upper + lower) / 2
Es gibt zwei Möglichkeiten, um mit der Suche fortzufahren. Da es schwierig ist, in Briefen zu erklären, werde ich den Code veröffentlichen.
Array-Manipulation.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
Index.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
Ist es für jeden so? Abhängig von der while-Bedingung muss es nicht do-while sein. Es gibt keinen großen Unterschied im Erscheinungsbild, und es scheint, dass Sie es mögen, aber Array-Operationen sind schwer zu verarbeiten und sollten vermieden werden.
Der folgende Code schreibt dieses Problem neu, damit Sie leicht vergleichen können, was in jeder Sprache geschrieben wurde. Wie oben erwähnt, verwenden wir den Index des Arrays und drehen ihn in einer Schleife. Swift ist diesmal geschlossen, da keine Swift-Teilnehmer anwesend waren.
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