再帰なしでJavaでバイナリ検索アルゴリズムを実装する方法

ソートされた配列内の要素を見つけるための一般的なバイナリ検索アルゴリズムの反復実装。

みなさん、こんにちは!私は自分のブログにたくさんのアルゴリズムとデータ構造の記事を公開しましたが、これはここで最初のものです。この記事では、インタビューでよく使われる基本的なアルゴリズムについて説明します。

はい、あなたはそれを正しく推測しました。Javaでバイナリ検索を実装する必要があり、反復と再帰の両方のバイナリ検索アルゴリズムを作成する必要があります。

コンピュータサイエンスでは、バイナリ検索、または半間隔検索は、分割統治アルゴリズムであり、並べ替えられた配列内のアイテムの位置を特定します。二分探索は、入力値を配列の中央の要素と比較することによって機能します。

比較により、要素が入力に等しいか、入力よりも小さいか、または入力よりも大きいかが判別されます。

比較される要素が入力と等しくなると、検索は停止し、通常は要素の位置を返します。

要素が入力と等しくない場合は、入力が要素よりも小さいか大きいかを判断するために比較が行われます。

結果に応じて、アルゴリズムは最初からやり直しますが、配列の要素の上位または下位のサブセットのみを検索します。

入力が配列内にない場合、アルゴリズムは通常、-1のようにこれを示す一意の値を出力するか、NoValueFoundExceptionのようにJavaでRuntimeExceptionをスローします。

バイナリ検索アルゴリズムは、通常、連続する反復ごとにチェックするアイテムの数を半分にします。したがって、対数時間で特定のアイテムを特定します(またはその不在を判別します)。

ところで、基本的な検索と並べ替えのアルゴリズムに慣れていない場合は、「データ構造とアルゴリズム:Java使用した詳細」などのコースに参加して基本的なアルゴリズムを学ぶこともできます。

Javaが言語の選択ではない場合は、このアルゴリズムコースのリストでJavaScriptとPythonに関するその他の推奨事項を見つけることができます。

ところで、本が好きなら、Thomas H.CormenによるIntroductiontoAlgorithmsのような包括的なアルゴリズムの本を読むことをお勧めします。

Javaでの反復二分探索のロジックを示すサンプルコードを次に示します

Javaでのバイナリ検索の実装

これは、Javaでバイナリ検索を実装するためのサンプルプログラムです。アルゴリズムは再帰的に実装されます。また、Javaでのバイナリ検索の実装について知っておくべき興味深い事実は、有名なEffectiveJavaの本の著者であるJoshuaBlochが「java.util.Arrays」でバイナリ検索を書いたことです。

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

これで、Javaで再帰を使用してバイナリ検索を実装する方法について説明しました。線形検索に加えて、これらはコンピュータサイエンスのクラスで学ぶ重要な検索アルゴリズムの2つです。

二分探索木のデータ構造は、このアルゴリズムを利用してデータを階層構造に配置し、O(logN)時間で任意のノードを検索できるようにします。

Though, you must remember that in order to use binary search, you need a sorted list or array, so you also need to consider the cost of sorting when you consider using binary search algorithm in the real world.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures — Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

10 Algorithms books for Interviews

10 Data Structure and Algorithm Courses for Interviews

5 Free Courses to Learn Data Structure and Algorithms

Other Data Structure and Algorithms tutorials you may like

  • How to implement Quicksort algorithm in place in Java? (tutorial)
  • How to implement Binary Search Tree in Java? (solution)
  • How to implement Quicksort algorithm without recursion? (tutorial)
  • How to implement Insertion sort algorithm in Java? (tutorial)
  • How to implement Bubble sort algorithm in Java? (tutorial)
  • What is the difference between Comparison and Non-Comparison based sorting algorithm? (answer)
  • How to implement Bucket Sort in Java? (tutorial)
  • How to implement a Binary Search Algorithm without recursion in Java? (tutorial)
  • 50+ Data Structure and Algorithms Courses for Programmers (questions)

Thanks for reading this article. If you like this article then please share with your friends and colleagues. If you have any suggestion or feedback then please drop a comment.

P.S. — If you are serious about improving your Algorithms skills, I think the Data Structures and Algorithms: Deep Dive Using Java is the best one to start with.