البحث الثنائي في المصفوفة

Question

كيف يمكنني تنفيذ بحث ثنائي باستخدام مصفوفة فقط؟

Answer 1

وتأكد من أن مجموعة الخاصة بك يتم فرز لأن هذا هو جوهر عملية بحث ثنائي.

وأي مفهرسة / وصول عشوائي بنية بيانات يمكن أن يكون ثنائي البحث. لذلك عندما تقول باستخدام "مجرد مجموعة"، وأود أن أقول صفائف بنية البيانات أبسط / المشترك الذي يعمل بحث ثنائي على.

ويمكنك أن تفعل ذلك بشكل متكرر (أسهل) أو بشكل متكرر. تعقيد وقت بحث ثنائي O (تسجيل 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
}

Answer 2

وهذا يعتمد إذا كان لديك تكرار عنصر واحد في مجموعة أو لا وإذا كنت تهتم نتائج متعددة أم لا. لدي طريقتين في هذا التنفيذ. واحد منهم يعود النتيجة الأولى فقط، ولكن الآخر بإرجاع كافة النتائج من المفتاح.

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 . وآمل أن يساعد.

Answer 3

والنسخة المقارنة واحد سريع ومختصر

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 4

هل تنفيذ أدناه التعليمات البرمجية في جافا وبسيطة وسريعة     / **      * ثنائي البحث باستخدام العودية      *author asharda      *      * /     الطبقة العامة BinSearch {

  /**
   * Simplistic BInary Search using Recursion
   * @param arr
   * @param low
   * @param high
   * @param num
   * @return int
   */
  public int binSearch(int []arr,int low,int high,int num)
  {
    int mid=low+high/2;
    if(num >arr[high] || num <arr[low])
    {
      return -1;
    }

    while(low<high)
    {
      if(num==arr[mid])
      {
        return mid;

      }
      else  if(num<arr[mid])
      {
       return  binSearch(arr,low,high-1, num);
      }

      else  if(num>arr[mid])
      {
        return binSearch(arr,low+1,high, num);
      }

    }//end of while

    return -1;
  }

  public static void main(String args[])
  {
    int arr[]= {2,4,6,8,10};
    BinSearch s=new BinSearch();
    int n=s.binSearch(arr, 0, arr.length-1, 10);
    String result= n>1?"Number found at "+n:"Number not found";
    System.out.println(result);
  }
}

Answer 5

البحث الثنائي في جافا سكريبت (ES6)

(إذا كان أي شخص يحتاج)

تصاعدي:

function binarySearch (arr, val) {
    let start = 0;
    let end = arr.length - 1;
    let mid;

    while (start <= end) {
        mid = Math.floor((start + end) / 2);

        if (arr[mid] === val) {
            return mid;
        }
        if (val < arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

العودية:

function binarySearch(arr, val, start = 0, end = arr.length - 1) {
    const mid = Math.floor((start + end) / 2);

    if (val === arr[mid]) {
        return mid;
    }
    if (start >= end) {
        return -1;
    }
    return val < arr[mid]
        ? binarySearch(arr, val, start, mid - 1)
        : binarySearch(arr, val, mid + 1, end);
}