java二分查找

末蓝、 2022-07-12 09:16 138阅读 0赞

转 ： [http://jayzotion.javaeye.com/blog/404084][http_jayzotion.javaeye.com_blog_404084]

1.  public class TestBinSearch \{   
2.    
3.      /\*\*  
4.       \* @param args  
5.       \*/  
6.      public static void main(String\[\] args) \{   
7.          // TODO Auto-generated method stub   
8.          int a\[\] = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \};   
9.    
10.         System.out.println(binSearch(a, 0, a.length - 1, 100));   
11.     \}   
12.   
13.     // 二分查找递归实现   
14.     public static int binSearch(int a\[\], int start, int end, int key) \{   
15.   
16.         int mid = (end - start) / 2 + start;   
17.         if (a\[mid\] == key) \{   
18.             return mid;   
19.         \}   
20.         if (start >= end) \{   
21.             return -1;   
22.   
23.         \} else if (a\[mid\] < key) \{   
24.             return binSearch(a, mid + 1, end, key);   
25.         \} else if (a\[mid\] > key) \{   
26.             return binSearch(a, start, mid - 1, key);   
27.         \}   
28.         return -1;   
29.   
30.     \}   
31.   
32.     // 二分查找普通循环实现   
33.     public static int binSearch(int a\[\], int key) \{   
34.   
35.         int mid = a.length / 2;   
36.         if (key == a\[mid\]) \{   
37.             return mid;   
38.         \}   
39.   
40.         int start = 0;   
41.         int end = a.length - 1;   
42.         while (start <= end) \{   
43.             mid = (end - start) / 2 + start;   
44.   
45.             if (key < a\[mid\]) \{   
46.   
47.                 end = mid - 1;   
48.             \} else if (key > a\[mid\]) \{   
49.   
50.                 start = mid + 1;   
51.             \} else \{   
52.                 return mid;   
53.             \}   
54.         \}   
55.         return -1;   
56.     \}   
57. \}

[http_jayzotion.javaeye.com_blog_404084]: http://jayzotion.javaeye.com/blog/404084