1. public class ArrayDemo
   
2. {
   
3.         public static void main (String args [])
   
4.         {
   
5.                 int [] arr = {1,5,6,7,9,12,45,65,789};
   
6.                 int index = halfSearch(arr,65);
   
7.                 int index2 = halfSearch_2(arr,65);
   
8.                 int index3 = halfSearch_3(arr,8);
   
9.                 System.out.println(index);
   
10.                 System.out.println(index2);
    
11.                 System.out.println(index3);
    
12.         }
    
13.         //折半查找1
    
14.         public static int halfSearch(int [] arr, int x)
    
15.         {
    
16.                 int min = 0;
    
17.                 int max = arr.length-1;
    
18.                 int mid = (min+max)/2;
    
19.                 while (arr[mid]!=x)
    
20.                 {
    
21.                         mid = (max+min)/2;  //计算出mid的值，不然这个代码就没有意义。
    
22.                         if (x<arr[mid])
    
23.                                 max = mid-1;
    
24.                         else if (x>arr[mid])
    
25.                                 min = mid+1;
    
26.                         if (max<min)
    
27.                                 return -1;
    
28.                 }
    
29.                 return mid;
    
30.         }
    
31.         //折半查找2
    
32.                 public static int halfSearch_2(int [] arr, int x)
    
33.         {
    
34.                 int min = 0;
    
35.                 int max = arr.length-1;
    
36.                 int mid = (min+max)/2;
    
37.                 while (min<=max)
    
38.                 {
    
39.                         mid = (max+min)>>1;  //右移一位，相当于除以2，比较快速
    
40.                         if (x<arr[mid])
    
41.                                 max = mid-1;
    
42.                         else if (x>arr[mid])
    
43.                                 min = mid+1;
    
44.                         else
    
45.                                 return mid;   //只剩下x=arr[mid]的情况，返回mid就行
    
46. 
    
47.                 }
    
48.                 return -1;  //min>max的情况直接返回-1。
    
49.         }
    
50.         /*
    
51.         需求：在数组{1,5,6,7,9,12,45,65,789}中，存储一个元素，
    
52.         保证这个数组还是有序的，这个元素存储的位置角标怎么获取？
    
53.         */
    
54.         public static int halfSearch_3(int [] arr, int x)
    
55.         {
    
56.                 int min = 0;
    
57.                 int max = arr.length-1;
    
58.                 int mid = (min+max)/2;
    
59.                 while (min<=max)
    
60.                 {
    
61.                         mid = (max+min)>>1;  //右移一位，相当于除以2，比较快速
    
62.                         if (x<arr[mid])
    
63.                                 max = mid-1;
    
64.                         else if (x>arr[mid])
    
65.                                 min = mid+1;
    
66.                         else
    
67.                                 return mid;   //只剩下x=arr[mid]的情况，返回mid就行
    
68. 
    
69.                 }
    
70.                 return min;   //min现在所在的位置就是该元素应该存储的位置。
    
71.         }
    
72. }

复制代码

经典基础代码

灵界 发表于 2015-6-2 21:16
经典基础代码

晚上看毕老师视频，白天自己理解着写的。