我该如何仅使用数组来实现二分查找？
在数组中进行二分查找
16
- Claudiu
2
请查看此链接：http://www.msccomputerscience.com/2013/01/binary-search.html - ARJUN
对我来说这很有意义。除了数组，你还可以使用二叉树。 - symbiont
11个回答
42
请确保数组已排序，因为这是二分查找的关键。
任何索引/随机访问数据结构都可以进行二分查找。所以，当你说“只使用一个数组”时，我会说数组是二分查找最基本/常见的数据结构。
您可以使用递归（最简单）或迭代方法进行二分查找。二分搜索的时间复杂度为O(log N)，比线性搜索每个元素检查的O(N)要快得多。以下是来自维基百科的一些示例：二分查找算法：
递归方法：
BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = low + ((high - low) / 2)
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
迭代：
BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = low + ((high - low) / 2)
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}
- Simucal
6
1在计算中间值时，请注意溢出情况。（请参见http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html） - Firas Assaad
1@Firas Assad，谢谢，我已更新代码以显示防止溢出的修复。 - mmcdole
2
mid = low + ((high - low) / 2) 和 mid = (low + high) / 2 是相同的。虽然整数除法可能会产生疑问，但算法使用这两个公式仍然有效。 - Niklas R2@NiklasR 除非
low+high 会导致整数溢出。 - jarno(mid = (high - low) / 2) 这样不行吗？ - AlphaGoku
@AlphaGoku 不，不可以。
假设数组中没有中间点，则会有两个中间点，我们必须选择较低的中间点。因此，您应始终选择公式 int mid = low + ((high - low)/2) 来计算下限中间值，因为它更可靠。参考资料 https://hackernoon.com/binary-search-in-detail-914944a1434a - habib
2
Javascript（ES6）中的二分查找
（如果有人需要）
自下而上：
function binarySearch (arr, val) {
let start = 0;
let end = arr.length - 1;
let mid;
while (start <= end) {
mid = Math.floor((start + end) / 2);
if (arr[mid] === val) {
return mid;
}
if (val < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
递归:
function binarySearch(arr, val, start = 0, end = arr.length - 1) {
const mid = Math.floor((start + end) / 2);
if (val === arr[mid]) {
return mid;
}
if (start >= end) {
return -1;
}
return val < arr[mid]
? binarySearch(arr, val, start, mid - 1)
: binarySearch(arr, val, mid + 1, end);
}
- Lior Elrom
1
使用仅数组实现二分查找
二分查找是一种优化的解决方案，用于在数组中搜索元素，因为它通过以下三种方式减少了搜索时间:
- 要么要搜索的元素可以是中间元素。
- 如果不是中间元素，则小于中间元素
- 如果两种情况都不成立，则大于中间元素
如果上述任何情况不满足，则此类元素不存在于数组中。
二分查找的好处
- 不需要搜索整个数组。只需搜索到中间或小于中间或大于中间即可。节省搜索时间。
算法步骤
步骤1：使用数组中最低索引和最高索引的floor计算
mid index。步骤2：将要搜索的元素与位于
middle index的元素进行比较。步骤3：如果步骤2不满足，则检查所有左侧元素。为此，请将
high index = mid index - 1步骤4：如果步骤3不满足，则检查所有右侧元素。为此，请将
low index = mid index + 1
如果没有满足的情况，则返回-1，这意味着要搜索的元素不存在于整个数组中。
代码
# iterative approach of binary search
def binary_search(array, element_to_search):
n = len(array)
low = 0
high = n - 1
while low <= high:
mid = (low + high) // 2
if element_to_search == array[mid]:
return mid
elif element_to_search < array[mid]:
high = mid - 1
elif element_to_search > array[mid]:
low = mid + 1
return -1
array = [1, 3, 5, 7]
element_to_search = 8
print(binary_search(array=array,
element_to_search=element_to_search))
递归代码也可以用于二分查找。无论是迭代还是递归，时间复杂度都为O(logn)，但是在考虑空间复杂度时，迭代方法将获胜，因为它只需要O(1)的空间复杂度，而对于递归算法，函数调用栈中将使用三个函数调用，因此空间复杂度变为O(logn)。下面是递归解决方案。
def recurs_binary_search(arr, element, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == element:
return mid
elif arr[mid] > element:
return recurs_binary_search(arr,element, low, mid - 1)
else:
return recurs_binary_search(arr,element, mid + 1, high)
array = [1, 3, 5, 7]
element_to_search = 7
low = 0
high = len(array) - 1
print(recurs_binary_search(arr=array, element=element_to_search,
low=low, high=high))
- Sanpreet
1
在Java中实现二分查找算法
二分查找算法的伪代码流程：
将起始索引（low）设置为0，结束索引（high）设置为数组长度减1。
当起始索引小于等于结束索引时：
a. 计算中间索引为起始索引和结束索引的平均值：mid = (low + high) / 2。 b. 将中间元素与目标值进行比较： - 如果它们相等，则返回中间元素的索引。 - 如果中间元素大于目标值，则将结束索引更新为mid - 1。 - 如果中间元素小于目标值，则将起始索引更新为mid + 1。
如果未找到目标值，则返回一个表示目标值不在数组中的值。
The Iterative Approach
public int binarySearch(int[] arr, int size, int key){
int startIndex = 0;
int endIndex = arr.length - 1;
int midIndex = startIndex + (endIndex-startIndex)/2 ;
while (startIndex <= endIndex){
if(key == arr[midIndex]) {
return midIndex;
}else if (key > arr[midIndex]){
startIndex = midIndex + 1;
}else {
endIndex = midIndex -1;
}
midIndex = startIndex + (endIndex-startIndex)/2 ;
}
return -1; // Target element not found
}
The Recursive Approach
public int binarySearchByRecursion(int[] arr, int key, int startIndex, int endIndex){
if(startIndex > endIndex){
return -1;
}
int midIndex = startIndex + (endIndex - startIndex) / 2;
if(key == arr[midIndex]) {
return midIndex;
}else if (key > arr[midIndex]){
return binarySearchByRecursion( arr, key, midIndex + 1, endIndex);
}else {
return binarySearchByRecursion(arr, key, startIndex, midIndex -1);
}
}
在这里发现全面的解决方案 https://github.com/Amir36036/ds/blob/array/src/main/java/org/ds/array/BinarySearch.java
- Amir Shaikh
0
在Java中实现了下面的代码，简单而快速 /** * 使用递归进行二分查找 * 作者：asharda * */ public class BinSearch {
/**
* Simplistic BInary Search using Recursion
* @param arr
* @param low
* @param high
* @param num
* @return int
*/
public int binSearch(int []arr,int low,int high,int num)
{
int mid=low+high/2;
if(num >arr[high] || num <arr[low])
{
return -1;
}
while(low<high)
{
if(num==arr[mid])
{
return mid;
}
else if(num<arr[mid])
{
return binSearch(arr,low,high-1, num);
}
else if(num>arr[mid])
{
return binSearch(arr,low+1,high, num);
}
}//end of while
return -1;
}
public static void main(String args[])
{
int arr[]= {2,4,6,8,10};
BinSearch s=new BinSearch();
int n=s.binSearch(arr, 0, arr.length-1, 10);
String result= n>1?"Number found at "+n:"Number not found";
System.out.println(result);
}
}
- user7258708
1
int mid=(low+high)/2;
return binSearch(arr,low,mid-1,num);
return binSearch(arr,mid+1,high,num); - qulinxao
0
这要看你的数组中是否有一个元素重复以及你是否在意多个找到的情况。我在这个实现中有两种方法。其中一种只返回第一个找到的结果，而另一种则返回关键字的所有发现。
import java.util.Arrays;
public class BinarySearchExample {
//Find one occurrence
public static int indexOf(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
//Find all occurrence
public static void PrintIndicesForValue(int[] numbers, int target) {
if (numbers == null)
return;
int low = 0, high = numbers.length - 1;
// get the start index of target number
int startIndex = -1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] > target) {
high = mid - 1;
} else if (numbers[mid] == target) {
startIndex = mid;
high = mid - 1;
} else
low = mid + 1;
}
// get the end index of target number
int endIndex = -1;
low = 0;
high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] > target) {
high = mid - 1;
} else if (numbers[mid] == target) {
endIndex = mid;
low = mid + 1;
} else
low = mid + 1;
}
if (startIndex != -1 && endIndex != -1){
System.out.print("All: ");
for(int i=0; i+startIndex<=endIndex;i++){
if(i>0)
System.out.print(',');
System.out.print(i+startIndex);
}
}
}
public static void main(String[] args) {
// read the integers from a file
int[] arr = {23,34,12,24,266,1,3,66,78,93,22,24,25,27};
Boolean[] arrFlag = new Boolean[arr.length];
Arrays.fill(arrFlag,false);
// sort the array
Arrays.sort(arr);
//Search
System.out.print("Array: ");
for(int i=0; i<arr.length; i++)
if(i != arr.length-1){
System.out.print(arr[i]+",");
}else{
System.out.print(arr[i]);
}
System.out.println("\nOnly one: "+indexOf(arr,24));
PrintIndicesForValue(arr,24);
}
}
更多信息，请访问https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/BinarySearchExample.java。希望能对您有所帮助。
- Mohammad
0
这里是Python编程语言的简单解决方案：
def bin(search, h, l):
mid = (h+l)//2
if m[mid] == search:
return mid
else:
if l == h:
return -1
elif search > m[mid]:
l = mid+1
return bin(search, h, l)
elif search < m[mid]:
h = mid-1
return bin(search, h, l)
m = [1,2,3,4,5,6,7,8]
tot = len(m)
print(bin(10, len(m)-1, 0))
以下是流程：
- 获取中间点
- 如果中间点等于搜索值，则返回中间点
- 否则，如果高低点相同，则返回-1
- 如果搜索值大于中间点，则将mid point+1作为较低值
- 如果搜索值小于中间点，则将mid point-1作为较高值
- bhargav3vedi
0
假设数组已排序，这里是一个具有O(log n)运行时复杂度的Pythonic答案：
def binary_search(nums: List[int], target: int) -> int:
n = len(nums) - 1
left = 0
right = n
while left <= right:
mid = left + (right - left) // 2
if target == nums[mid]:
return mid
elif target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1
- Niyousha Mohammadshafie
0
二分查找的短循环：
function search( nums, target){
for(let mid,look,p=[0,,nums.length-1]; p[0]<=p[2]; p[look+1]=mid-look){
mid = (p[0] + p[2])>>>1
look = Math.sign(nums[mid]-target)
if(!look)
return mid
}
return -1
}
想法是替换：
if(nums[mid]==target)
return mid
else if(nums[mid]>target)
right = mid - 1
else //here must nums[mid]<target
left = mid + 1
如果观察前者相等，使用更多的默契（可能计算量较少）：
switch(dir=Math.sign(nums[mid]-target)){
case -1: left = mid - dir;break;
case 0: return mid
case 1: right = mid - dir;break;
}
所以如果左、中、右变量依次排列，我们可以通过 C 指针的方式使用 &mid[-1,0,1] 来访问它们：
dir=Math.sign(nums[mid]-target)
&mid[dir] = mid - dir
现在我们已经得到了循环体，因此我们可以构建二分查找：
while(dir && left <= right){
mid = (left + right)>>>2
dir=Math.sign(nums[mid]-target)
&mid[dir] = mid - dir
}
过了一会儿我们就：
return [dir,mid]
具有语义的
for dir == -1 then nums[mid]<target<nums[mid+1] // if nums[mid+1 ] in start seaching domain
for dir == 0 then mid is place of target in array
for dir == 1 then nums[mid-1]<target<nums[mid] // if nums[mid-1 ] in start seaching domain
因此，在一些更人性化的伪代码JavaScript函数中等效：
function search( nums, target){
let dir=!0,[left, mid, right]=[0, , nums.length-1]
while(dir && left <=right){
mid = (left + right)>>>1
dir = Math.sign(nums[mid]-target)
&mid[dir]=mid - dir
}
return [dir, mid]
}
对于js语法，我们需要使用q={'-1':0,1:nums.length-1}，其中q[-1]表示左侧名称，q[0]表示中间，q[1]表示右侧，或者对于所有三个元素都是q[dir]。
或者对于从0开始的数组索引也可以这样：
我们可以使用p=[0,,nums.length-1]，其中p[0]表示左侧昵称，p[1]表示中间，p[2]表示右侧，对于所有三个元素都是p[1+dir]。
. :)
- qulinxao
1
1感谢您提供答案。您是否可以编辑您的答案并包含代码解释？这将有助于未来的读者更好地理解正在发生的事情，特别是那些对该语言感到陌生并且难以理解概念的社区成员。 - Jeremy Caney
0
单个比较版本快速且简洁
int bsearch_double(const double a[], int n, double v) {
int low = 0, mid;
while (n - low > 1) {
mid = low + (n - low) / 2;
if (v < a[mid]) n = mid;
else low = mid;
}
return (low < n && a[low] == v) ? low : -1;
}
- Jed
3
1如果这是一个要求，那么只需要一个
if 语句。 - Jed最后还应该检查a[n]，否则可能无法从{0,1}中找到例如1。 - jarno
1@jarno 在C语言中，
n通常表示数组的长度（从0开始），因此a[n]是无效的。与此同时，bsearch_double((double[]){0,1}, 2, 1)是有效的，并返回1。 - Jed网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接