一个有序数组,如果其中有重复的数，那么要查找这个数的位置的话，用一般查找的方法可以查找到这个数第一次出现的角标,那么如果使用折半查找呢？找出来的角标是哪个呢？还是第一次出现的角标吗？

也是可以查到第一个出现的角标的啊while(start<end)
     {
         pos=(start+end)/2;
         if(a[pos]==num)  end=pos;//这里检测到要查的数字之后，不停止循环。
         else if(a[pos]<num) start=pos+1;
         else end=pos-1;
     }
if(a[start]==num) return start;//知道折半的开始位为要查的数字时才返回。

使用折半查找的话，有可能是第一个，也有可能是第二个或者其他的。主要是看你的重复的数的角标位置。

1. public class Index
   
2. {
   
3. 
   
4. public static int halfSearch(int b [],int key)
   
5. {
   
6. int max=b.length-1,min=0,mid;
   
7. while(min<=max)
   
8. {
   
9. mid=(max+min)>>1;
   
10. if(key>b[mid])
    
11. {
    
12. mid=mid+1;
    
13. }
    
14. else if(key<b[mid])
    
15. {
    
16. min=mid-1;
    
17. }
    
18. else
    
19. {
    
20. return mid;
    
21. }
    
22. 
    
23. }
    
24. return -1;
    
25. }
    
26. 
    
27. 
    
28. public static void main(String[] args)
    
29. {
    
30. 
    
31. int [] arr =new int[]{2,5,6,5,9,1};
    
32. int index=halfSearch(arr,5);
    
33. System.out.println("index="+index);
    
34. }
    
35. 
    
36. }
    

复制代码

我的
结果是：index=3，，，是第二个数的角标

＂O_忆_O 发表于 2013-7-9 13:44  也是可以查到第一个出现的角标的啊while(start

这个代码有点难懂啊

楼上的不是有序数组，如果是有序数组折半查找也是元素一次出现的角标位置；

1. public class Demo1 {
   
2.         public static void main(String[] args) {
   
3.                 int[] arr = {1,2,4,5,6,6,8,9};
   
4.                 System.out.println("index= " + halfSearch(arr,6));
   
5.         }
   
6. 
   
7.         public static int halfSearch(int[] arr,int num) {       
   
8.                 int min = 0,max = arr.length-1,mid = (max+min)/2;                                               
   
9.                 while(arr[mid] != num) {                                                                                                               
   
10.                         if(num > arr[mid]) {                                       
    
11.                                 min = mid+1;                                                       
    
12.                         }else if(num < arr[mid]) {                                       
    
13.                                 max = mid-1;
    
14.                         }
    
15.                         if(min > max)                                                               
    
16.                                 return -1;
    
17.                         else
    
18.                                 mid = (max+min)/2;                                               
    
19.                 }
    
20.                 return mid;
    
21.         }
    
22. }

复制代码

崔龙飞 发表于 2013-7-9 20:54  楼上的不是有序数组，如果是有序数组折半查找也是元素一次出现的角标位置； ...

你这个出来是第二个位置呀。

杜天伟 发表于 2013-7-9 21:27
你这个出来是第二个位置呀。

汗，是的额。我运行的时候理解成第mid个元素了，重新运行了不同的数，都是第二个数的角标，你是遇到这方面的题了吗？

崔龙飞 发表于 2013-7-10 00:19  汗，是的额。我运行的时候理解成第mid个元素了，重新运行了不同的数，都是第二个数的角标，你是遇到这方 ...

不是，我是看到这块的时候突然想到的这个问题。有点好奇如果有相同数，找出来会是第几个