バイナリ検索配列が重複して含まれている場合

Question

こんにちは、

我々はバイナリ検索を使用して、以下の配列の24を検索する場合、検索キーのインデックスものです。

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

私は配列は誰もが明確values.Can重複している場合、それは働くんか...あなたが提案

Answer 1

配列が途中インデックスに目標値を持っていることを、バイナリサーチに関する疑問を持っています最も効率的な実装では、第1レベルの再帰の前にこの値を返します。この実装は '5'（中間インデックス）を返します。

アルゴリズムを理解するには、デバッガでコードをステップ実行してください。 @Pleepleusによって指摘

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

Answer 2

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

Answer 3

としては再帰自体の最初のレベルからのインデックス5を返します。

：あなたは次のアルゴリズムを使用する要素の lower_boundまたは upper_boundを検索したい場合は mid = left + (right-left)/2

を使用し、代わりにmid = (left + right)/2を使用しての

1. ：しかし、私は、バイナリ検索についてのいくつかのことを指摘したいと思います

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