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

Answer 1

你實際上並沒有與陣列值進行比較。在

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

Answer 2

這裏

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

Answer 3

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

Answer 4

我找到某種迭代版本不是很容易讀懂，遞歸使得它很好的和容易:-)

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

} 

Answer 5

這是一個沒有堆的解決方案。同樣的事情可以在一個數組中完成。 如果我們需要找到'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; 
    } 

Answer 6

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

或

Binary Search in Array

Answer 7

/** 
    * 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; 
     } 

    } 

Answer 8

/** 
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"); 
} 
}