Dizi İçinde İkili Arama

Question

Sadece bir diziyi kullanarak ikili bir aramayı nasıl uygularım?

Answer 1

Dizininizin sıralı olduğundan emin olun, çünkü bu bir ikili aramanın temelidir.

Herhangi bir endeksli/rastgele erişimli veri yapısı ikili olarak aranabilir. Yani "sadece bir dizi" kullanarak söylediğinizde, dizilerin bir ikili aramanın kullanıldığı en temel/ortak veri yapısı olduğunu söyleyebilirim.

Bunu yinelemeli (en kolay) veya yinelemeli olarak yapabilirsiniz. Bir ikili aramanın zaman karmaşıklığı O (N) 'deki her bir elemanı kontrol etmenin doğrusal bir aramasından çok daha hızlı olan O (log N)' dir. İşte bazı örnekler Wikipedia: Binary Search Algorithm gelmektedir:

Recursive:

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 
    } 

Iteratif:

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

tek karşılaştırma sürümü Size tekrarını varsa bağlıdır

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

hızlı ve özlü Dizininizde veya bir öğenizdeki tek bir öğenin ve birden fazla bulguya önem verdiğinizde veya olmasın. Bu uygulamada iki yöntemim var. Bunlardan biri sadece ilk bulguyu döndürür, ancak diğeri anahtarın tüm bulgularını döndürür.

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

    } 

} 

Daha fazla bilgi için lütfen https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/BinarySearchExample.java adresini ziyaret edin. Umut ediyorum bu yardım eder.