黑马程序员技术交流社区

标题: 数组中插入数值的问题 [打印本页]

---

作者: 刘家斌    时间: 2014-10-13 16:57
标题: 数组中插入数值的问题

1. public static int chaRu(int[] arr,int num)
   
2.         {
   
3.                 int min=0,max=arr.length,mid;
   
4.                 while(min<=max)
   
5.                 {
   
6.                         mid=(min+max)/2;
   
7.                         if(arr[mid]>num)
   
8.                                 max=mid-1;
   
9.                         else if(arr[mid]<num)
   
10.                                 min=mid+1;
    
11.                         else
    
12.                                 return mid;
    
13.                 }
    
14.                 return min;//输出最小角标，就是插入的角标号
    

复制代码

在一个有序数组中插入一个数值，求插入的位置，为什么返回的是min呢？

---

作者: Mr.Ni    时间: 2014-10-13 18:13
为什么返回值是min:折半查找结束的条件是什么？（不考虑num与arr[mid]相等的情况下）
当max<min时，循环结束。在此之前的循环过程中最小角标右移最大角标左移，两者相互靠拢。
直到有min=max，此时mid=min=max,此时也判断出num比前一个数arr[mid-1}的数要大，比后一个数arr[mid+1]的数要小，那么num和这最后一个数值进行比较，当num的值小于arr[mid]，此时的max=mid-1，最大角标值左移，最小角标不动，循环结束，而此时的最小角标值就是所要插入的角标，插入后，原来位置上比num大的值自动右移；num的值大于arr[mid]，此时的min=mid+1，最大角标不动，最小角标右移，把num插入在右移后的最小角标上，比前一个数大，而原来位置上的数是大于num的，再插入的时候自动右移了。

---

作者: nyk    时间: 2014-10-13 18:39
走几遍程序就会发现，最后需要插入的位置是min，因为/计算符号的结果偏0

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2