数组中的二分查找

Question

如何仅使用数组来实现二分搜索？

Answer 1

确保您的数组已排序，因为这是二分搜索的关键。

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

您可以递归（最简单）或迭代地执行此操作。 二分搜索的时间复杂度为 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
}

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

Answer 3

仅使用数组实现二分搜索

二分搜索是搜索数组中元素的优化解决方案，因为它通过以下三种方式减少搜索时间

• 要么要搜索的元素可以是中间元素。
• 如果不是 middle 则将小于 middle
• 如果两种情况都不成立则将大于 middle

如果不满足上述任何一种情况，则该元素不存在于数组中。

二分查找的好处

• 不需要搜索整个数组。 搜索到中间或小于中间或大于中间。 节省搜索时间。

算法步骤

• 第1步：使用最低索引和最高索引的下限计算中间索引一个数组。

• 第 2 步：将要搜索的元素与中间索引处存在的元素进行比较

• 第 3 步： 如果第 2 步 不满足，则检查中间元素左侧的所有元素。 为此，等于高索引 = 中索引 - 1

• 步骤 4： 如果不满足步骤 3，则检查所有元素到中间元素的右侧。 为此，等于低索引 = 中索引 + 1

如果不满足任何情况，则等于低索引=中索引+ 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))

Answer 4

用Java实现二分查找算法

二分搜索算法的伪代码流程：

---

1. 将起始索引（低位）设置为 0，将结束索引（高位）设置为数组长度减 1。

2. 当起始索引小于或等于结束索引时：

• ： 将中间指数计算为开始指数和结束指数的平均值：mid = (low + high) / 2
• 。 将中间元素与目标值进行比较：
  • 如果相等，则返回中间元素的索引。
  • 如果中间元素大于目标值，则将结束索引更新为 mid - 1。
  • 如果中间元素小于目标值，则将起始索引更新为 mid + 1。

3. 如果未找到目标值，则返回值表明它不存在于数组中。

---

迭代方法

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
    }

递归方法

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

Answer 5

这取决于您的数组中是否重复某个元素，以及您是否关心多个结果。 我在这个实现中有两种方法。 其中一个仅返回第一个发现，而另一个则返回该键的所有发现。

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 6

单一比较版本快速简洁

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

Answer 7

用Java实现了下面的代码，简单快速
/**
* 使用递归进行二分查找
* @作者阿沙达
*
*/
公共类 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);
  }
}

Answer 8

这是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，
• 如果搜索值大于中点，则返回中点 +1 为较低值，则使中点-1 为较高值
• 如果搜索值小于中点，

Answer 9

二分搜索的短循环：

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

所以如果 left、mid、right 变量按顺序排列，我们可以对所有变量进行寻址，在 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 sintax，我们需要使用 q={'-1':0,1:nums.length-1} 其中 q[ 的左侧名称-1]，q[0] 的中间，q[1] 的右边，或者所有 3 的 q 是 q[dir]

或从 0 开始的数组索引相同：

我们可以使用 p=[0,,nums.length- 1] 其中左侧是 p[0] 的昵称，中间是 p[1] 的昵称，右侧是 p[2] 的昵称，这三个昵称是 p[1+dir]

。 :)

Answer 10

假设数组已排序，这是一个运行时复杂度为 O(log n) 的 Python 答案：

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

Answer 11

注意，数组需要排序！

我认为这是一个简单的方法，仅使用值来查找和数组。

递归：

def bin_search(value, arr):
    
    hlf = len(arr)//2
    if len(arr) > 1:
        if value == arr[hlf]:
            return True
        elif value < arr[hlf]:
             return bin_search(value,arr[0:hlf])
        elif value > arr[hlf]:
             return bin_search(value,arr[hlf:])
    if len(arr) == 1:
        return value == arr[hlf]

迭代：

def bin_search_iter(arr,value):

    found = False

    for i in range(arr[0],arr[len(arr)//2]):
        
        found = value == arr[0] or value == arr[len(arr)//2]
        
        if found or len(arr) == 1:
            break

        elif value > arr[len(arr)//2]:
            arr = arr[len(arr)//2:]
            print(">",arr)
            
        elif value < arr[len(arr)//2]:
            arr = arr[:len(arr)//2]
            print("<",arr)
            
    return found

都很容易阅读，没有高低索引和 n 的对数，因为它每次都会将数组减半