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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 聖手`书生 中级黑马   /  2013-4-2 10:33  /  2451 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 聖手`书生 于 2013-4-6 18:35 编辑
  1. class ArrayTest4
  2. {
  3.         public static void main(String[] args)
  4.         {
  5. //                int[] arr = {3,2,1,5,4,2,9};
  6. //                int index = getIndex(arr,2);
  7. //                System.out.println("index="+index);

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

  9.                 int index = getIndex_2(arr,190);
  10.                 System.out.println("index="+index);
  11.         public static int getIndex_2(int[] arr,int key)
  12.         {
  13.                 int min = 0,max = arr.length-1,mid;

  14.                 while(min<=max)
  15.                 {
  16.                         mid = (max+min)>>1;

  17.                         if(key>arr[mid])
  18.                                 min = mid + 1;
  19.                         else if(key<arr[mid])
  20.                                 max = mid - 1;
  21.                         else
  22.                                 return mid;
  23.                 }
  24.                 return min;
  25.         }
复制代码
练习:有一个有序的数组,想要将一个元素插入到该数组中,
还要保证该数组是有序的。如何获取该元素在数组中的位置。

现在就是想问大家一下,代码中的mid = (max+min)>>1;右移一位操作,怎么就是相当于(max+min)/2操作,有什么依据。

5 个回复

倒序浏览
本帖最后由 邵震 于 2013-4-2 10:57 编辑

因为二进制每个位数代表的数是以乘二递增的  也就是128 64 32 16 8 4 2 1

假设是8要进行>>1运算  
8的二进制表现形式是1000  对应着8001  你右移一位就是0100对应0400所以右移一位等于进行除二运算

代码一会给你

大体思路就是进行对比找到比比你要加进去的数大的那个数加在他后面 后面的数往后顺移
回复 使用道具 举报
mid = (max+min)>>1;这个是位运算,
向右移动一位就是,右边的一位舍弃,左边补零.比如:
0000 0110       这个是6
>>1,即向右移1位,得到
0000 0011       这个是3
其实,你只要记住:
向左移n位就是乘以2的n次方;
向右移n位就是除以2的n次方;
回复 使用道具 举报
二楼给你说了主要意思,其实也就那么点意思。三楼给你补充了一下。
你可以自己用代码写出了,验证一下对不对...
回复 使用道具 举报
mid = (max+min)>>1右移一位,右移一位不就是除于2的一次方吗,2的一次方不就是2吗,这不就等于 (max+min)/2吗
回复 使用道具 举报
你可以看看计算机组成原理。。。上面讲的很清楚。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马