java實現遞歸算法_如何在Java中實現二進制搜索算法而無需遞歸

java實現遞歸算法

by javinpaul

由javinpaul

流行的二進制搜索算法的迭代實現，用于在排序數組中查找元素。 (An Iterative implementation of the popular binary search algorithm to find an element in a sorted array.)

Hello everyone! I have published a lot of algorithms and data structure articles on my blog, but this one is the first one here. In this article, we’ll examine popular fundamental algorithms for interviews.

大家好！我在博客上發表了很多算法和數據結構文章，但這是本文的第一篇。在本文中，我們將研究流行的基本面試算法。

Yes, you guessed it right: you need to implement a binary search in Java, and you need to write both iterative and recursive binary search algorithms.

是的，您猜對了：您需要在Java中實現二進制搜索 ，并且需要編寫迭代和遞歸二進制搜索算法。

In computer science, a binary search, or half-interval search, is a divide and conquer algorithm that locates the position of an item in a sorted array. Binary searching works by comparing an input value to the middle element of the array.

在計算機科學中，二進制搜索或半間隔搜索是一種分而治之的算法 ，用于定位項目在已排序數組中的位置。二進制搜索通過將輸入值與數組的中間元素進行比較來工作。

The comparison determines whether the element equals the input, is less than the input, or is greater than the input.

比較將確定元素等于輸入，小于輸入還是大于輸入。

When the element being compared equals the input, the search stops and typically returns the position of the element.

當要比較的元素等于輸入時，搜索將停止，并且通常會返回該元素的位置。

If the element is not equal to the input, then a comparison is made to determine whether the input is less than or greater than the element.

如果元素不等于輸入，則進行比較以確定輸入是否小于或大于元素。

Depending on the result, the algorithm then starts over again, but only searching the top or a bottom subset of the array’s elements.

然后根據結果，算法重新開始，但僅搜索數組元素的頂部或底部子集。

If the input is not located within the array, the algorithm will usually output a unique value indicating this like -1 or just throw a RuntimeException in Java like NoValueFoundException.

如果輸入不在數組內，則算法通常會輸出一個唯一的值，例如-1，或者僅在Java中拋出RuntimeException ，例如NoValueFoundException。

Binary search algorithms typically halve the number of items to check with each successive iteration, thus locating the given item (or determining its absence) in logarithmic time.

二進制搜索算法通常將每次連續迭代要檢查的項目數量減半，從而在對數時間內定位給定的項目(或確定其不存在)。

Btw, if you are not familiar with fundamental search and sort algorithms, then you can also join a course like Data Structures and Algorithms: Deep Dive Using Java to learn fundamental algorithms.

順便說一句，如果您不熟悉基本搜索和排序算法，那么您也可以參加“ 數據結構和算法：使用Java深入學習”一門課程，學習基本算法。

If Java is not your choice of language, you can find more recommendations for JavaScript and Python in this list of algorithms courses.

如果您不是Java語言的選擇者，則可以在此算法課程列表中找到有關JavaScript和Python的更多建議。

Btw, if you prefer books, I suggest you read a comprehensive algorithm book like Introduction to Algorithms by Thomas H. Cormen.

順便說一句，如果您喜歡書籍，我建議您閱讀全面的算法書籍，例如Thomas H. Cormen的《 算法簡介》 。

Here is some sample code which shows the logic of iterative binary search in Java:

這是一些示例代碼，顯示了Java中迭代二進制搜索的邏輯：

Java二進制搜索實現 (Binary Search Implementation in Java)

Here is a sample program to implement binary search in Java. The algorithm is implemented recursively. Also, an interesting fact to know about binary search implementation in Java is that Joshua Bloch, author of the famous Effective Java book, wrote the binary search in “java.util.Arrays”.

這是在Java中實現二進制搜索的示例程序。該算法是遞歸實現的。另外，有關Java中二進制搜索實現的一個有趣事實是，著名的Effective Java著作的作者Joshua Bloch在“ 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.

That’s all about how to implement binary search using recursion in Java. Along with Linear search, these are two of the essential search algorithms you learn in your computer science class.

這就是如何在Java中使用遞歸實現二進制搜索的全部內容。與線性搜索一起，這是您在計算機科學課上學習的兩種基本搜索算法。

The binary search tree data structure takes advantage of this algorithm and arranges data in a hierarchical structure so that you can search any node in O(logN) time.

二進制搜索樹數據結構利用此算法，并以分層結構排列數據，以便您可以在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 Kabutz10 Algorithms books for Interviews10 Data Structure and Algorithm Courses for Interviews5 Free Courses to Learn Data Structure and Algorithms

但是，您必須記住，要使用二進制搜索，您需要一個排序列表或數組，因此在現實世界中考慮使用二進制搜索算法時，還需要考慮排序的成本。 進一步學習 數據結構和算法：使用Java 算法和數據結構的深入研究— Java的第1部分和第2部分。Heinz Kabutz編寫的Java 9中的數據結構。10 面試的算法書 10 面試的數據結構和算法課程 5項學習數據結構和算法的免費課程

Other Data Structure and Algorithms tutorials you may like

您可能喜歡的其他數據結構和算法教程

How to implement Quicksort algorithm in place in Java? (tutorial)
如何在Java中實現Quicksort算法？ ( 教程 )
How to implement Binary Search Tree in Java? (solution)
如何在Java中實現二進制搜索樹？ ( 解決方案 )
How to implement Quicksort algorithm without recursion? (tutorial)
如何實現無遞歸的Quicksort算法？ ( 教程 )
How to implement Insertion sort algorithm in Java? (tutorial)
如何在Java中實現插入排序算法？ ( 教程 )
How to implement Bubble sort algorithm in Java? (tutorial)
如何在Java中實現冒泡排序算法？ ( 教程 )
What is the difference between Comparison and Non-Comparison based sorting algorithm? (answer)
基于比較和基于非比較的排序算法有什么區別？ ( 回答 )
How to implement Bucket Sort in Java? (tutorial)
如何在Java中實現Bucket Sort？ ( 教程 )
How to implement a Binary Search Algorithm without recursion in Java? (tutorial)
如何在Java中實現沒有遞歸的二進制搜索算法？ ( 教程 )
50+ Data Structure and Algorithms Courses for Programmers (questions)
面向程序員的50多種數據結構和算法課程( 問題 )

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.

感謝您閱讀本文。如果您喜歡這篇文章，請與您的朋友和同事分享。如果您有任何建議或反饋，請發表評論。