Двоичный поиск в массиве

Question

Как бы реализовать двоичный поиск, используя только массив?

Answer 1

Убедитесь, что ваш массив отсортирован, так как это сложность двоичного поиска.

Любая структура данных с индексированным/произвольным доступом может быть двоичной. Поэтому, когда вы говорите, используя «просто массив», я бы сказал, что массивы - это самая простая/общая структура данных, в которой используется двоичный поиск.

Вы можете сделать это рекурсивно (проще) или итеративно. Сложность времени двоичного поиска - O (log N), которая значительно быстрее, чем линейный поиск проверки каждого элемента в O (N). Вот некоторые примеры из Wikipedia: Binary Search Algorithm:

Рекурсивные:

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

Единственная версия сравнения быстро и сжато

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 3

Это зависит, если у вас есть повторение одного элемента в вашем массиве или нет, и если вы заботитесь о нескольких результатах или нет. У меня есть два метода в этой реализации. Один из них возвращает только первое обнаружение, но другой возвращает все результаты ключа.

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. Я надеюсь, что это помогает.