java - Java BinarySearch

Question

助けてもらえますか？これを機能させるために多くの方法を試しましたが、配列を並べ替えて印刷しましたが、その後、バイナリ検索関数を実行したくなく、正しい結果が得られませんでした。それは常に私に-1を与えます。何か助けはありますか？

public class BinarySearch {
public static final int NOT_FOUND = -1;
public static int binarySearch(double[] a, double key) {
    int low = 0;
    int high = a.length -1;
    int mid;
    while (low<=high) {
        mid = (low+high) /2;
        if (mid > key) 
            high = mid -1;
        else if (mid < key) 
            low = mid +1;
        else 
            return mid;
    }
    return NOT_FOUND;
}
public static void main(String[] args) {
    double key = 10.5, index;
    double a[] ={10,5,4,10.5,30.5};
    int i;
    int l = a.length;
    int j;
    System.out.println("The array currently looks like");
    for (i=0; i<a.length; i++)
        System.out.println(a[i]);
    System.out.println("The array after sorting looks like");
    for (j=1; j < l; j++) {
        for (i=0; i < l-j; i++) {
            if (a[i] > a[i+1]) {
                double temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
    for (i=0;i < l;i++) {
        System.out.println(a[i]);
    }
    System.out.println("Found " + key + " at " + binarySearch(double a[], key));
}   
}

score 12 · Accepted Answer

実際には配列値と比較していません。の

while (low <= high) {
      mid = (low + high) / 2;
      if (mid > key) {
          high = mid - 1;
      } else if (mid < key) {
          low = mid + 1;
      } else {
          return mid;
      }
}

代わりにこのセクションを使用してください

    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] > key) {
            high = mid - 1;
        } else if (a[mid] < key) {
            low = mid + 1;
        } else {
            return mid;
        }
    }

インデックスを見つけるのは正しかったのですが、インデックス番号とキーを比較しているだけで、明らかに間違っています。あなたが書くとき、a[mid]あなたは実際にあなたの鍵をインデックスにある番号と比較するでしょうmid。

また、コードの最後の行でコンパイルエラーが発生しています。

System.out.println("Found " + key + " at " + binarySearch(a, key));

score 1 · Accepted Answer

ここ

    if (mid > key) 
        high = mid -1;
    else if (mid < key) 
        low = mid +1;
    else 
        return mid;

インデックスを配列内の値（キー）と比較しています。代わりにそれを比較する必要がありますa[mid]

と、

System.out.println("Found " + key + " at " + binarySearch(double a[], key));

する必要があります

System.out.println("Found " + key + " at " + binarySearch(a, key));

score 1 · Accepted Answer

public static double binarySearch(double[] a, double key) {

    if (a.length == 0) {
      return -1;
    }
    int low = 0;
    int high = a.length-1;

    while(low <= high) {
      int middle = (low+high) /2; 
      if (b> a[middle]){
        low = middle +1;
      } else if (b< a[middle]){
        high = middle -1;
      } else { // The element has been found
        return a[middle]; 
      }
    }
    return -1;
  }

score 1 · Accepted Answer

int binarySearch(int list[], int lowIndex, int highIndex, int find)
    {
        if (highIndex>=lowIndex)
        {
            int mid = lowIndex + (highIndex - lowIndex)/2;

            // If the element is present at the
            // middle itself
            if (list[mid] == find)
                return mid;

            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (list[mid] > find)
                return binarySearch(list, lowIndex, mid-1, find);

            // Else the element can only be present
            // in right subarray
            return binarySearch(list, mid+1, highIndex, find);
        }

        // We reach here when element is not present
        //  in array
        return -1;
    }

score 0 · Accepted Answer

私はどういうわけか、反復バージョンはあまり読みにくいと思います。再帰はそれを素晴らしく簡単にします:-)

public class BinarySearch {

    private static int binarySearchMain(int key, int[] arr, int start, int end) {
        int middle = (end-start+1)/2 + start; //get index of the middle element of a particular array portion

        if (arr[middle] == key) {
            return middle;
        }

        if (key < arr[middle] && middle > 0) {
            return binarySearchMain(key, arr, start, middle-1); //recurse lower half
        }

        if (key > arr[middle] && middle < arr.length-1) {
            return binarySearchMain(key, arr, middle+1, end); //recurse higher half
        }

        return Integer.MAX_VALUE; 
    }

    public static int binarySearch(int key, int[] arr) { //entry point here
        return binarySearchMain(key, arr, 0, arr.length-1);
    }

}

score 0 · Accepted Answer

これがヒープのないソリューションです。同じことが配列でも実行できます。'k'の最大数を見つける必要がある場合は、メインデータソースから最初のk個のアイテムが入力されたサイズ'k'の配列を取得します。ここで、アイテムを読み続け、場所がある場合は結果配列に配置します。

public static void largestkNumbers() {
    int k = 4;    // find 4 largest numbers
    int[] arr = {4,90,7,10,-5,34,98,1,2};
    int[] result = new int[k];

    //initial formation of elems
    for (int i = 0; i < k; ++i) {
      result[i] = arr[i];
    }
    Arrays.sort(result);

    for ( int i = k; i < arr.length; ++i ) {
      int index = binarySearch(result, arr[i]);
      if (index > 0) {
        // insert arr[i] at result[index] and remove result[0]
        insertInBetweenArray(result, index, arr[i]);
      }
    }
  }

  public static void insertInBetweenArray(int[] arr, int index, int num) {
    // insert num at arr[index] and remove arr[0]
    for ( int i = 0 ; i < index; ++i ) {
      arr[i] = arr[i+1];
    }
    arr[index-1] = num;
  }

  public static int binarySearch(int[] arr, int num) {

    int lo = 0;
    int hi = arr.length - 1;
    int mid = -1;

    while( lo <= hi ) {
      mid = (lo+hi)/2;
      if ( arr[mid] > num ) {
        hi = mid-1;
      } else if ( arr[mid] < num ) {
        lo = mid+1;
      } else {
        return mid;
      }
    }
    return mid;
  }

score 0 · Accepted Answer

int BinSearch(int[] array, int size, int value)
{
    if(size == 0) return -1;
    if(array[size-1] == value) return size-1;
    if(array[0] == value) return 0;
    if(size % 2 == 0) {
        if(array[size-1] == value) return size-1;
        BinSearch(array,size-1,value);
    }
    else
    {
        if(array[size/2] == value) return (size/2);
        else if(array[size/2] > value) return BinSearch(array, (size/2)+1, value);
    else if(array[size/2] < value) return (size/2)+BinSearch(array+size/2, size/2, value);
    }
}

また

配列の二分探索

score 0 · Accepted Answer

   /**
     * Find whether 67 is a prime no
     * Domain consists 25 of prime numbers
     * Binary Search
     */

    int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

    int min = 0,
            mid,
            max = primes.length,
            key = 67,
            count= 0;

    boolean isFound = false;


    while (!isFound) {
        if (count < 6) {
          mid = (min + max) / 2;
            if (primes[mid] == key) {
                isFound = true;
                System.out.println("Found prime at: " + mid);
            } else if (primes[mid] < key) {
                min = mid + 1; 
                isFound = false;
            } else if (primes[mid] > key) { 
                max = mid - 1; 
                isFound = false;
            }
            count++;

        } else {
            System.out.println("No such number");
            isFound = true;
        }

    }

score 0 · Accepted Answer

/**
HOPE YOU LIKE IT
A.K.A Binary Search
Take number array of 10 elements, input a number a check whether the number 
is present:
**/
package array;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
class BinaryS
{
    public static void main(String args[]) throws IOException
    {       
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));      
    System.out.print("Enter a number: ");
    int n=Integer.parseInt(br.readLine());
    int a[]={10,20,30,40,50,60,70,80,90,100};
    int upper=a.length-1,lower=0,mid;
    boolean found=false;
    int pos=0;
    while(lower<=upper)
    {
        mid=(upper+lower)/2;
        if(n<a[mid])upper=mid-1;
        else if(n>a[mid])lower=mid+1;
        else
        {
            found=true;
            pos=mid;
            break;
        }
    }
    if(found)System.out.println(n+" found at index "+pos);
    else System.out.println(n+" not found in array");
}
}

score 0 · Accepted Answer

私はこの答えをずっと後で投稿していることを知っています。しかし、私によれば、最初に境界条件をチェックする方が
常に良いとのことです。これにより、アルゴリズムがより効率的になります。

    public static int binarySearch(int[] array, int element){
    if(array == null || array.length == 0){  // validate array
        return -1;
    }else if(element<array[0] || element > array[array.length-1]){ // validate value our of range that to be search 
        return -1;
    }else if(element == array[0]){  // if element present at very first element of array
        return 0;
    }else if(element == array[array.length-1]){ // if element present at very last element of array
        return array.length-1;
    }

    int start = 0;
    int end = array.length-1;

    while (start<=end){
        int midIndex = start + ((end-start)/2);   // calculate midIndex
        if(element < array[midIndex]){  // focus on left side of midIndex
            end = midIndex-1;
        }else if(element > array[midIndex]){// focus on right side of midIndex
            start = midIndex+1;
        }else {
            return midIndex;   // You are in luck :)
        }
    }
    return -1; // better luck next time :(
}

score 0 · Accepted Answer

static int binarySearchAlgorithm() {
        // Array should be in sorted order. Mandatory requirement
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int lowIndex = 0;
        int valueToFind = 8;
        int highIndex = a.length - 1;

        while (lowIndex <= highIndex) {
            //Finding the midIndex;
            int midIndex = (highIndex + lowIndex) / 2;
            // Checking if midIndex value of array contains the value to be find.
            if (a[midIndex] == valueToFind) {
                return midIndex;
            } 
            // Checking the mid Index value is less than the value to be find.
            else if (a[midIndex] < valueToFind) {
                // If Yes, changing the lowIndex value to midIndex value + 1;
                lowIndex = midIndex + 1;
            } else if (a[midIndex] > valueToFind) {
                // If Yes, changing the highIndex value to midIndex value - 1;
                highIndex = midIndex - 1;
            } else {
                return -1;
            }
        }
        return -1;
    }

java - Java BinarySearch

11 に答える 11

Related

Reference