数组中的二进制search

我将如何实现一个二进制search只使用一个数组？

Answer 1

确保您的数组已sorting，因为这是二进制search的关键。

任何索引/随机访问数据结构都可以进行二进制search。 所以当你说使用“只是一个数组”时，我会说数组是二进制search所采用的最基本/常见的数据结构。

你可以recursion地（最简单的）或者迭代的方式来完成它。 二进制search的时间复杂度为O（log N），这比检查O（N）处的每个元素的线性search快得多。 这里有一些来自维基百科的例子：二进制searchalgorithm ：

recursion：

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 } 

Answer 2

这取决于你是否有重复的数组中的一个元素或否，如果你关心多个调查结果与否。 在这个实现中我有两个方法。 其中之一只返回第一个发现，而另一个返回关键的所有发现。

 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 。 我希望它有帮助。

Answer 3

单一的比较版本是快速和简洁的

 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; }