后端开发教程 - Java、Spring Boot 实战 - msg200.com
用于编码面试的迭代二分搜索算法
披露：本篇文章包含附属链接；如果您通过本文提供的不同链接购买产品或服务，我可能会收到报酬。
大家好！我在我的博客上发布过很多关于编程面试的算法和数据结构文章，但这篇文章是这里最早的几篇之一。在本文中，我们将探讨一些面试中常用的基础算法。
是的，你猜对了：我说的是二分查找算法，它是一种基础的查找算法，既不太容易也不太难。该算法很容易用递归实现，这就是为什么大多数面试官会要求你实现一个不使用递归的二分查找算法，也称为迭代二分查找，而这正是你将在本教程中学习的内容。
在计算机科学中，二分查找（或称半区间查找）是一种分而治之的算法，用于定位已排序数组中某个元素的位置。二分查找的工作原理是将输入值与数组的中间元素进行比较。
比较确定元素是否等于输入、小于输入或大于输入。
当被比较的元素等于输入时，搜索停止并通常返回元素的位置。
如果元素不等于输入，则进行比较以确定输入是否小于或大于元素。
根据结果，算法重新开始，但仅搜索数组元素的顶部或底部子集。
如果输入不在数组内，算法通常会输出一个唯一值来表示这一点，如 -1，或者只是在 Java 中抛出一个RuntimeException，如 NoValueFoundException。
二分搜索算法通常将每次连续迭代中要检查的项目数量减半，从而在对数时间内找到给定的项目（或确定其不存在）。
顺便说一句，如果您不熟悉基本的搜索和排序算法，那么您也可以参加像数据结构和算法：使用 Java 深入研究这样的课程来学习基本算法。
如果 Java 不是您选择的语言，您可以在此算法课程列表中找到更多关于 JavaScript 和 Python 的推荐。
顺便说一句，如果你更喜欢书籍，我建议你阅读一本综合性的算法书籍，例如Thomas H. Cormen 的《算法导论》。
下面是一些示例代码，展示了Java 中迭代二分查找的逻辑：
Java 中非递归的二分查找
下面是一个用 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");
}
}
}
**Output**
Binary Search 12 in integer array [12, 23, 31, 43]
12 found at location 0
Binary Search 43 in integer array [12, 23, 31, 43]
43 found at location 3
Binary Search 331 in integer array [123, 243, 331, 1298]
331 found at location 2
Binary Search 331 in integer array [123, 243, 331, 1298]
1333 is not present in the list.
这就是如何在 Java 中不使用递归实现二分查找的全部内容。除了线性查找之外，这些都是你在计算机科学课程中应该学习的两种基本查找算法。
这些不仅从编码面试的角度来看很重要，而且对于理解其他基本数据结构（如二叉搜索树或 BST）也很重要。
二叉搜索树数据结构利用了该算法，并将数据排列成层次结构，以便您可以在 O(logN) 时间内搜索任何节点。
不过，您必须记住，为了使用二分搜索，您需要一个排序列表或排序数组，因此当您考虑在现实世界中使用二分搜索算法时，您还需要考虑排序的成本。
进一步学习
数据结构和算法：深入使用 Java
算法和数据结构 - 第 1 部分和第 2 部分
Heinz Kabutz 编写的 Java 9 中的数据结构
10 本用于面试的算法书籍
10 门用于面试的数据结构和算法课程
5 门学习数据结构和算法的免费课程
Java 中的数据结构：面试复习
编程工作面试中的其他数据结构和算法问题
- 如何在 Java 中实现快速排序算法？（教程）
- 如何在 Java 中实现二叉搜索树？（解决方案）
- 如何实现不带递归的快速排序算法？（教程）
- 如何用 Java 实现插入排序算法？（教程）
- 如何在 Java 中实现冒泡排序算法？（教程）
- 基于比较和非比较的排序算法有什么区别？ （回答）
- 如何在 Java 中实现桶排序？（教程）
- 如何在 Java 中实现不带递归的二分查找算法？（教程）
- 50+ 面向程序员的数据结构和算法课程（问题）
感谢您阅读本文。如果您喜欢这篇文章，请与您的朋友和同事分享。如果您有任何建议或反馈，请发表评论。
鏂囩珷鏉ユ簮锛�https://dev.to/javinpaul/iterative-binary-search-algorithm-for-coding-interviews-1p20PS - 如果您真的想提高您的算法技能，我认为《数据结构和算法：使用 Java 深入研究》是最好的入门书。