实现二分法查找——java实现

时间:2022-10-27 18:06:19

java实现二分法查找,前提:要求待查找的数组已经是按照升序排好的。

package test;


public class test {
		  public static void main(String[] args) {
			  int[] list = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
			  int i = BinarySearch.binarySearch(list, 2); // Returns 0
			  System.out.println(i);

			  int j = BinarySearch.binarySearch(list, 11); // Returns 4
			  System.out.println(j);
			  int k = BinarySearch.binarySearch(list, 12); // Returns –6
			  System.out.println(k);
			  int l = BinarySearch.binarySearch(list, 1); // Returns –1
			  System.out.println(l);
			  int m = BinarySearch.binarySearch(list, 3); // Returns –2	  
			  System.out.println(l);
		  }
}
class BinarySearch {

	  /** Use binary search to find the key in the list */
		  public static int binarySearch(int[] list, int key) {
		    int low = 0;
		    int high = list.length - 1;

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

		    return -low - 1; // Now high < low
		  }
	}

结果:

0
4
-6
-1
-1