一道面试题是这样子的：请在一个有序数组中插入一个元素，使之也有序，并且返回它的位置。

我的想法比较复杂是这样的：将数组存入链表。通过链表的查找算法找到比这个元素大的一个数，将这个元素插入链表，，最后返回位置。这样问题迎刃而解。
今天看了毕向东老师的视频：解决方案更优如下。直接通过二分折半查找寻找要插入的这个元素，不管找没找到，函数都会返回这个元素的位置。描述不大清楚，详见代码如图：

直接Arrays工具类        binarySearch(int[] int k)方法

我也查看了这个

折半查找。。。。。。。。。

用折半查找的方式寻找该元素在数组中的位置，
如果存在，就在这位置后面插入该元素，
如果不存在，在mid后面插入改元素

学习了还可以这样啊

1. 
   
2. /**
   
3. * @author Administrator
   
4. * 用折半查找法插入一个元素到一个有序数组并使之有序，返回该元素的位置
   
5. */
   
6. public class HalfSearchTest {
   
7.         
   
8.         public static int halfSearch(int[] arr, int num){
   
9.                 int min = 0;int max = arr.length-1; int mid;
   
10.                 while(min<=max){
    
11.                         mid = (min+max) >> 1;
    
12.                         if(num<arr[mid]){
    
13.                                 max = mid - 1;
    
14.                                 
    
15.                         }else if(num>arr[mid]){
    
16.                                 min = mid + 1;
    
17.                         }else
    
18.                                 return mid;
    
19.                         
    
20.                 }
    
21.                
    
22.                 return min;
    
23.                
    
24.         }
    
25.         
    
26.         public static void main(String[] args){
    
27.                
    
28.                 int[] arr ={1,2,3,4,7};
    
29.                 System.out.print(halfSearch(arr,6));
    
30.         }
    
31. 
    
32. }
    

复制代码

应该是这样的（升序情况）