1. ------<a  target="blank">Java培训、Android培训、iOS培训、.Net培训</a>、期待与您交流！ -------
   
2. //数组的查找练习
   
3. class ArrayTest4
   
4. {
   
5.         public static void main(String[] args)
   
6.         {
   
7.                 int[] arr = {3,5,13,15,16,18,55};
   
8.                 int index = halfSearch_1(arr,18);
   
9.                 System.out.println(index);
   
10.                 //把17插入到数组中时，输出它应该所在位置的下标；
    
11.                 int index2 = getIndex(arr,17);
    
12.                 System.out.println(index2);
    
13. 
    
14.         }
    
15.         /*
    
16.         折半查找，提高效率，但是必须是针对有序的数组
    
17.         */
    
18.         //方法一：
    
19.         public static int halfSearch_1(int[] arr,int key)
    
20.         {       
    
21.                 //定义三个整型的值，分别表示数组开头元素的下标、
    
22.                 //中间元素的下标，以及最后元素的下标。
    
23.                 int min,max,mid;
    
24.                 min = 0;
    
25.                 max = arr.length-1;
    
26.                 mid = (max+min)/2;
    
27.                 while(arr[mid]!=key)
    
28.                 {
    
29.                         if(key>arr[mid])
    
30.                                 min = mid + 1;
    
31.                         else if(key<arr[mid])
    
32.                                 max = mid - 1;
    
33.                         if(min>max)
    
34.                                 return -1;
    
35.                         mid = (max+min)/2;
    
36.                 }
    
37.                 return mid;
    
38.         }
    
39.         //方法二：
    
40.         public static int halfSearch_2(int[] arr,int key)
    
41.         {
    
42.                 int min=0,max=arr.length-1,mid;
    
43.                 while(min<=max)
    
44.                 {
    
45.                         mid = (max + min)>>1;
    
46.                         if(key>arr[mid])
    
47.                                 min = mid + 1;
    
48.                         else if(key<arr[mid])
    
49.                                 max = mid - 1;
    
50.                         else
    
51.                                 return mid;
    
52.                 }
    
53.                 return -1;
    
54.         }
    
55.         /*
    
56.         在一个有序的数组中插入一个数，使的插入后这个数组仍然有序，给出插入位置的下标；
    
57.         */
    
58.         public static int getIndex(int[] arr,int key)
    
59.         {
    
60.                 int min=0,max=arr.length-1,mid;
    
61.                 while(min<=max)
    
62.                 {
    
63.                         mid = (max + min)>>1;
    
64.                         if(key>arr[mid])
    
65.                                 min = mid + 1;
    
66.                         else if(key<arr[mid])
    
67.                                 max = mid - 1;
    
68.                         else
    
69.                                 return mid;
    
70.                 }
    
71.                 return min;
    
72.         }
    
73. }
    

复制代码

1. ------<a  target="blank">Java培训、Android培训、iOS培训、.Net培训</a>、期待与您交流！ -------
   
2. //数组的查找练习
   
3. class ArrayTest4
   
4. {
   
5.         public static void main(String[] args)
   
6.         {
   
7.                 int[] arr = {3,5,13,15,16,18,55};
   
8.                 int index = halfSearch_1(arr,18);
   
9.                 System.out.println(index);
   
10.                 //把17插入到数组中时，输出它应该所在位置的下标；
    
11.                 int index2 = getIndex(arr,17);
    
12.                 System.out.println(index2);
    
13. 
    
14.         }
    
15.         /*
    
16.         折半查找，提高效率，但是必须是针对有序的数组
    
17.         */
    
18.         //方法一：
    
19.         public static int halfSearch_1(int[] arr,int key)
    
20.         {       
    
21.                 //定义三个整型的值，分别表示数组开头元素的下标、
    
22.                 //中间元素的下标，以及最后元素的下标。
    
23.                 int min,max,mid;
    
24.                 min = 0;
    
25.                 max = arr.length-1;
    
26.                 mid = (max+min)/2;
    
27.                 while(arr[mid]!=key)
    
28.                 {
    
29.                         if(key>arr[mid])
    
30.                                 min = mid + 1;
    
31.                         else if(key<arr[mid])
    
32.                                 max = mid - 1;
    
33.                         if(min>max)
    
34.                                 return -1;
    
35.                         mid = (max+min)/2;
    
36.                 }
    
37.                 return mid;
    
38.         }
    
39.         //方法二：
    
40.         public static int halfSearch_2(int[] arr,int key)
    
41.         {
    
42.                 int min=0,max=arr.length-1,mid;
    
43.                 while(min<=max)
    
44.                 {
    
45.                         mid = (max + min)>>1;
    
46.                         if(key>arr[mid])
    
47.                                 min = mid + 1;
    
48.                         else if(key<arr[mid])
    
49.                                 max = mid - 1;
    
50.                         else
    
51.                                 return mid;
    
52.                 }
    
53.                 return -1;
    
54.         }
    
55.         /*
    
56.         在一个有序的数组中插入一个数，使的插入后这个数组仍然有序，给出插入位置的下标；
    
57.         */
    
58.         public static int getIndex(int[] arr,int key)
    
59.         {
    
60.                 int min=0,max=arr.length-1,mid;
    
61.                 while(min<=max)
    
62.                 {
    
63.                         mid = (max + min)>>1;
    
64.                         if(key>arr[mid])
    
65.                                 min = mid + 1;
    
66.                         else if(key<arr[mid])
    
67.                                 max = mid - 1;
    
68.                         else
    
69.                                 return mid;
    
70.                 }
    
71.                 return min;
    
72.         }
    
73. }
    

复制代码