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

Ответ 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
}

Ответ 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;
}

Ответ 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. Надеюсь, это поможет.