Ignite

算法

2017-07-28

二分查找法

对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。
给定一个整数数组A及它的大小n,同时给定要查找的元素val,请返回它在数组中的位置(从0开始),若不存在该元素,
返回-1。若该元素出现多次,请返回第一次出现的位置

测试样例:

[1,3,5,7,9],5,3

返回 : 1

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// 因为已是有序数组,所以不必排序
int low=0,high=n-1,mid;
while(low<=high){
mid=(low+high)/2;
if(val<A[mid]){
high=mid-1;
}else if(val>A[mid]){
low=mid+1;

}else {
//处理两个相邻元素相等情况
if(mid>0&&A[mid]==A[mid-1])
return mid-1;
else return mid;
}
}
return -1;
}

public static void main(String[] args) {
int[] A={1,2,4,4,5,5,6};
n=a.length;
val=5;
int result=getPos(A, n, val);
System.out.println(result);
}
}
世界上有10种人

世界上有10种人,一种懂二进制,一种不懂。那么你知道两个int32整数m和n的二进制表达,有多少个位(bit)不同么?

public class Solution {
public static int countBitDiff(int m, int n) {
int k = m ^ n; //先将二者做异或运算,得到结果;
int num = 0;
while(k>0)
{ //统计一个整数k含有多少个1;
k &= (k-1);
num++;
}
return num;
}

public static void main(String[] args) {    		
		int b=count(1999,2299);
		System.out.println("-----"+b);
	}

}

举个例子:假如传入数据count(5,3);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        十进制     二进制
5 0 1 0 1
^ 位异或:对应位相反为一,相同为0
3 0 0 1 1
- - - - - - - - - - - -
6 0 1 1 0
n=1 & 与运算:对应位都为1,则结果为1,否则为0
5 0 1 0 1
- - - - - - - - - - - -
4 0 1 0 0
n=2 & 与运算:对应位都为1,则结果为1,否则为0
3 0 0 1 1
- - - - - - - - - - - -
0 0 0 0 0

当然结果为2了。

#####分析一下代码:

如果一个整数不为0,那么这个整数至少有一位是1。如果我们把这个整数减1,那么原来处在整数最右边的1就会变为0,原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子:一个二进制数1100,从右边数起第三位是处于最右边的一个1。减去1后,第三位变成0,它后面的两位0变成了1,而前面的1保持不变,因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算,从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说,把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1,就可以进行多少次这样的操作。

ps : 计算机基础,二进制减法

1
2
3
4
   1 1 0 0 0 0                      1 2 0 0 0
- 1 0 1 1 1 类比 3 9 9 9
- - - - - - - - <----- - - - - - - - -
1 1 0 0 1 8 0 0 1

知识点补充

Java 位运算(移位、位与、或、异或、非)

Java提供的位运算符有:左移( << )、右移( >> ) 、无符号右移( >>> ) 、位与( & ) 、位或( | )、位非( ~ )、位异或( ^ ),除了位非( ~ )是一元操作符外,其它的都是二元操作符。
  1. 左移( << )

Test1、将5左移2位:

1
2
3
4
5
6
7
8
[java]
package com.xcy;

public class Test {
   public static void main(String[] args) {
       System.out.println(5<<2);//运行结果是20
   }
}

运行结果是20,但是程序是怎样执行的呢?
首先会将5转为2进制表示形式(java中,整数默认就是int类型,也就是32位):
0000 0000 0000 0000 0000 0000 0000 0101           然后左移2位后,低位补0:
0000 0000 0000 0000 0000 0000 0001 0100           换算成10进制为20

  1. 右移( >> ) ,右移同理,只是方向不一样罢了(感觉和没说一样)
    [java]
    System.out.println(5>>2);//运行结果是1
    还是先将5转为2进制表示形式:
    0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位,高位补0:
    0000 0000 0000 0000 0000 0000 0000 0001
  2. 无符号右移( >>> )
    我们知道在Java中int类型占32位,可以表示一个正数,也可以表示一个负数。正数换算成二进制后的最高位为0,负数的二进制最高为为1
    例如  -5换算成二进制后为:
    1111 1111 1111 1111 1111 1111 1111 1011   (刚开始接触二进制时,不知道最高位是用来表示正负之分的,当时就总想不通。。明明算起来得到的就是一个正数-_-)
    我们分别对5进行右移3位、 -5进行右移3位和无符号右移3位:
1
2
3
4
5
6
7
8
9
10
[java]
package com.xcy;

public class Test {
   public static void main(String[] args) {
       System.out.println(5>>3);//结果是0
       System.out.println(-5>>3);//结果是-1
       System.out.println(-5>>>3);//结果是536870911
   }
}

我们来看看它的移位过程(可以通过其结果换算成二进制进行对比):

5换算成二进制:

0000 0000 0000 0000 0000 0000 0000 0101

5右移3位后结果为0,0的二进制为:

0000 0000 0000 0000 0000 0000 0000 0000        // (用0进行补位)

-5换算成二进制:

1111 1111 1111 1111 1111 1111 1111 1011

-5右移3位后结果为-1,-1的二进制为:

1111 1111 1111 1111 1111 1111 1111 1111   // (用1进行补位)

-5无符号右移3位后的结果 536870911 换算成二进制:
0001 1111 1111 1111 1111 1111 1111 1111   // (用0进行补位)

通过其结果转换成二进制后,我们可以发现,正数右移,高位用0补,负数右移,高位用1补,当负数
使用无符号右移时,用0进行部位(自然而然的,就由负数变成了正数了)
注意:笔者在这里说的是右移,高位补位的情况。正数或者负数左移,低位都是用0补。(自行测试)

最后,二进制的运算

参考(https://www.chinatax.gov.cn/jypx/jsjjczs/multiply.htm)

抽象类 与 接口
  • 抽象类:用abstract修饰,抽象类中可以没有抽象方法,但抽象方法肯定在抽象类中,且抽象方法定义时不能有方法体;抽象类不可以实例化只能通过继承在子类中实现其所有的抽象方法;抽象类如果不被继承就没有任何意义;抽象类为子类定义了一个公共类型,封装了子类中的重复内容。
  • 接口:同Interface关键字定义接口,是特殊的抽象类因为类中只包含抽象方法;接口中不能定义成员变量可以定义常量;接口是其通过其他类使用implements关键字定义实现类,一个类一旦实现接口就必须实现其中的所有抽象方法,一个类可以实现多个接口,接口名之间用逗号隔开即可;一个接口可以通过extends关键字继承另一个接口,与此同时继承了父类中的所有方法。
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章