二进制搜索，如果数组包含重复

问题描述：

是什么，如果我们使用二进制搜索以下数组中搜索24搜索键的索引。

array = [10,20,21,24,24,24,24,24,30,40,45]

我有一个关于二进制搜索是如何做的工作，如果一个阵列中有重复的values.Can任何人澄清...

你是问，“如果我要实现二进制搜索，并给出这个数组，并要求找到24指数，该怎么回报？”或者你问'如果我通过其他人执行二分搜索来运行这个数组，我懒得去做，返回值是什么？' – 2012-03-14 13:08:33

如果可能的话，你可以告诉这两种情况..这将不胜感激...... – 2012-03-14 13:11:11

显然结果将是数组[5]。 – 2012-03-14 13:27:04

答

您提出的阵列在中间指标目标值的疑问，而在最有效的实现中，将在第一级递归之前返回该值。这个实现会返回'5'（中间索引）。

要理解该算法，只需在调试器中执行代码即可。

public class BinarySearch { 
    public static int binarySearch(int[] array, int value, int left, int right) { 
      if (left > right) 
       return -1; 
      int middle = left + (right-left)/2; 
      if (array[middle] == value) 
       return middle; 
      else if (array[middle] > value) 
       return binarySearch(array, value, left, middle - 1); 
      else 
       return binarySearch(array, value, middle + 1, right);   
    } 

    public static void main(String[] args) { 
     int[] data = new int[] {10,20,21,24,24,24,24,24,30,40,45}; 

     System.out.println(binarySearch(data, 24, 0, data.length - 1)); 
    } 
}

答

public class a{ 
    public static int binarySearch(int[] array, int value, int left, int right) { 
      if (left > right) 
       return -1; 
      int middle = (left + right)/2; 
      if (array[middle] == value) 
     { 
      if(array[middle-1]<array[middle]) 
       return middle; 
       //return binarySearch(array, value, left, middle - 1); 
       else 
       return binarySearch(array, value, left, middle - 1); 
     } 
      else if (array[middle] > value) 
       return binarySearch(array, value, left, middle - 1); 
      else 
       return binarySearch(array, value, middle + 1, right);   
    } 
public static int binarySearch1(int[] array, int value, int left, int right) { 
      if (left > right) 
       return -1; 
      int middle = (left + right)/2; 
      if (array[middle] == value) 
     { 
      if(array[middle]<array[middle+1]) 
       return middle; 
       else 

        return binarySearch1(array, value, middle + 1, right);   
     } 
      else if (array[middle] > value) 
       return binarySearch1(array, value, left, middle - 1); 
      else 
       return binarySearch1(array, value, middle + 1, right);   
    } 

    public static void main(String[] args) { 
     int[] data = new int[] {10,20,21,24,24,24,24,24,30,40,45}; 


     System.out.println(binarySearch(data, 24, 0, data.length - 1));  //First Index 
     System.out.println(binarySearch1(data, 24, 0, data.length - 1)); //Last Index 
    } 
}

答

正如@Pleepleus指出它将从递归本身的第一级返回指数5。不过，我想指出几点关于二进制搜索：

使用mid = (left + right)/2的相反，使用mid = left + (right-left)/2

如果你要搜索lower_bound或元素使用的upper_bound如下算法：

binLowerBound(a, lo, hi, x) 
    if (lo > hi) 
    return lo; 

    mid = lo + (hi - lo)/2; 
    if (a[mid] == x) 
    return binLowerBound(a, lo, mid-1, x); 
    else if (a[mid] > x) 
    return binLowerBound(a, lo, mid-1, x); 
    else 
    return binLowerBound(a, mid+1, hi, x); 

binHigherBound(a, lo, hi, x) 
    if (lo > hi) 
    return lo; 
    mid = lo + (hi - lo)/2; 
    if (a[mid] == x) 
    return binHigherBound(a, mid+1, hi, x); 
    else if (a[mid] > x) 
    return binHigherBound(a, lo, mid-1, x); 
    else 
    return binHigherBound(a, mid+1, hi, x);

二进制搜索，如果数组包含重复

相关推荐