黑马程序员技术交流社区

标题: 通宵发问题数组常见操作-拆半查找的一个小疑惑回帖有将~ [打印本页]

作者: 李斌 时间: 2012-5-22 00:17
标题: 通宵发问题数组常见操作-拆半查找的一个小疑惑回帖有将~
不多说直接上毕老师源码

import java.util.*;
class ArrayTest4
{
public static void main(String[] args)
{

int[] arr = {2,4,5,7,8,19,32,45};//8

int index = getIndex_2(arr,190);
System.out.println("index="+index);

}

public static int getIndex_2(int[] arr,int key)
{
int min = 0,max = arr.length-1,mid;

while(min<=max)
{
mid = (max+min)>>1;

if(key>arr[mid])
min = mid + 1;
else if(key<arr[mid])
max = mid - 1;
else
return mid;
}
return min;
}

对于最后return min 表示有点小疑惑金币奉上求解释 ~~~~

作者: 谭威 时间: 2012-5-22 01:15
折半查找的基础上插入数字要保证数组的顺序..
第一次折半的时候 mid=(0+7)/2=3,索引3的位置为7，插入的8比7大，那么min就要向右移动一次min=mid+1=4,那么mid=(4+7)/2=5,索引5是19，拿8和19再比较，8比19小，所以max要向左移动max=(mid-1)=(5-1)=4;,现在mid=(min+max)/2=(4+4)/2=4.索引角标为4的数为8，8和8相等了 min=max了这时不能折半，可以直接返回-1，8插入的位置在7的后面，而不是已有8的后面，那个位置刚好是min=4,min代表的位置就是你刚好要插入8的位置[4]。

作者: 郭宁 时间: 2012-5-22 01:18
这个我还木有看呢~~~

作者: 郭宁 时间: 2012-5-22 01:19
不回答也给加分~~~ 楼主你太厚道啦{:soso_e116:}

作者: 杨康 时间: 2012-5-22 02:14
这是折半思想查一个数组中的某一个元素的角标为的逆运算，当然必须这个数组是升序数组才能用此方法。当查找素组中的一个元素的时候，最后一行的return是 -1，也就是说通过比较min与max的值，来查找这个元素在数组中的位置，当min>max时候，该元素不存在于该数组中。反过来想，想要插入一个不存在的元素到数组中，也就是当min>max的时候的那个min的值，就是这个元素应该插入的地方。
这两个是属于逆运算。

作者: 何阳 时间: 2012-5-22 02:23
public static int getIndex_2(int[] arr,int key)
      {
            int min = 0,max = arr.length-1,mid;

            while(min<=max)
            {
                     mid = (max+min)>>1;

                     if(key>arr[mid])
                              min = mid + 1;
                     else if(key<arr[mid])
                              max = mid - 1;
                     else
                              return mid;
            }
            return min;
      }

//因为此函数你定义了返回 int，所以必须有返回值
//执行代码如果min小于max 则不执行while循环，直接返回min
//那什么时候min会小于max呢？你传递的一个空的数组。就是没有这个数组，编译或报错
//因为定义数组必须初始化长度的。报空指针异常。
//这种情况几乎不存在，所以会执行while循环的。写return min的目的是说明这个函数有返回值
//因为你上面定义了要返回int类型的。编译在编译的时候不明确会不会执行while循环，所以你必要
//加一个返回值类型。

作者: 李海 时间: 2012-5-22 14:35
其实你画一个图的话你就会非常的清楚为什么要返回min的值？答案就是返回的这个min的值是你查找的这个数将要插入到数组中的位置也就是说如果你查找的数组中，有你要查找的数那我们就返回mid值此时这个mid=max+min>>1 并且 min=max 但是如果你查找的数组中没有你要查找的数那我们就返回这个将要插入到数组中的位置也是返回min的值

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

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