黑马程序员技术交流社区

标题: [资源分享]二分折半查找解决的一道面试题 [打印本页]
作者: zly1992008    时间: 2014-6-6 14:54
标题: [资源分享]二分折半查找解决的一道面试题
一道面试题是这样子的：请在一个有序数组中插入一个元素，使之也有序，并且返回它的位置。

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

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

解决方案

解决方案
作者: 谭荣强    时间: 2014-6-8 05:30
直接Arrays工具类        binarySearch(int[] int k)方法
作者: IStudying    时间: 2014-6-8 09:38
我也查看了这个
作者: 上杉    时间: 2014-6-8 10:05
折半查找。。。。。。。。。
作者: 愤怒的小蔡！    时间: 2014-6-8 11:31
用折半查找的方式寻找该元素在数组中的位置，
如果存在，就在这位置后面插入该元素，
如果不存在，在mid后面插入改元素
作者: 张志民    时间: 2014-6-8 12:02
学习了还可以这样啊
作者: pk49800    时间: 2014-6-8 13:14
本帖最后由 pk49800 于 2014-6-8 13:23 编辑

  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.         }

  32. }
复制代码

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



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