A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

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

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

QQ图片20140606144701.jpg (89.47 KB, 下载次数: 6)

解决方案

解决方案

6 个回复

倒序浏览
直接Arrays工具类        binarySearch(int[] int k)方法
回复 使用道具 举报
我也查看了这个
回复 使用道具 举报
折半查找。。。。。。。。。
回复 使用道具 举报
用折半查找的方式寻找该元素在数组中的位置,
如果存在,就在这位置后面插入该元素,
如果不存在,在mid后面插入改元素
回复 使用道具 举报
学习了还可以这样啊
回复 使用道具 举报
本帖最后由 pk49800 于 2014-6-8 13:23 编辑

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

  30. }
复制代码

应该是这样的(升序情况)
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马