二分查找之网易笔试题
二分查找-基本版本二分查找-演示结果二分查找-算法原理网易笔试题（类似题型）直接上代码演示结果
二分查找-基本版本
import java
.util
.Scanner
;
public class BinarySearchDemo {
public static void main(String
[] args
){
int[] a
= {90, 80, 70, 60, 50, 40, 30, 20, 10};
for(int i
=0;i
<a
.length
;i
++){
System
.out
.print(a
[i
]);
System
.out
.print(' ');
}
System
.out
.println();
Scanner scan
= new Scanner(System
.in
);
while(scan
.hasNext()){
int x
= scan
.nextInt();
int r
= myBinarySearch(a
, x
);
System
.out
.println(r
);
}
}
public static int myBinarySearch(int a
[], int target
){
int left
= 0;
int right
= a
.length
-1;
int mid
= 0;
boolean isDescend
= true;
if(a
[right
] > a
[left
]){
isDescend
= false;
}
while(left
< right
){
mid
= left
+ (right
-left
)/2;
if(target
== a
[mid
]){
return mid
;
}else if(target
< a
[mid
]){
if(isDescend
) {
left
= mid
+ 1;
}else {
right
= mid
- 1;
}
}else{
if(isDescend
) {
right
= mid
- 1;
}else{
left
= mid
+ 1;
}
}
}
if(target
== a
[left
]){
return left
;
}else{
return -1;
}
}
}
二分查找-演示结果
二分查找-算法原理
算法原理
网易笔试题（类似题型）
又到了丰收的季节，恰逢小易去牛牛的果园里游玩。牛牛常说他对整个果园的每个地方都了如指掌，小易不太相信，所以他想考考牛牛。在果园里有N堆苹果，每堆苹果的数量为ai，小易希望知道从左往右数第x个苹果是属于哪一堆的。牛牛觉得这个问题太简单，所以希望你来替他回答。
输入描述：
第一行一个数n(1 <= n <= 105)。 第二行n个数ai(1 <= ai <= 1000)，表示从左往右数第i堆有多少苹果 第三行一个数m(1 <= m <= 105)，表示有m次询问。 第四行m个数qi，表示小易希望知道第qi个苹果属于哪一堆。
输出描述：
m行，第i行输出第qi个苹果属于哪一堆。
输入例子1：
5
2 7 3 4 9
3
1 25 11
输出例子1：
1
5
3
直接上代码
import java
.util
.Scanner
;
public class NetEaseExam1 {
public static void main(String
[] args
) {
Scanner scan
= new Scanner(System
.in
);
int n
= scan
.nextInt();
int[] a
= new int[n
];
for(int i
=0;i
<n
;i
++){
a
[i
] = scan
.nextInt();
}
int m
= scan
.nextInt();
int[] q
= new int[m
];
for(int i
=0;i
<m
;i
++){
q
[i
] = scan
.nextInt();
}
int[] aAscend
= new int[n
];
aAscend
[0] = a
[0];
for(int i
=1;i
<n
;i
++){
aAscend
[i
] = aAscend
[i
-1] + a
[i
];
}
for(int i
=0;i
<m
;i
++){
int x
= q
[i
];
int idx
= myBinarySearch(aAscend
, x
);
System
.out
.println(idx
+1);
}
}
public static int myBinarySearch(int a
[], int target
){
int left
= 0;
int right
= a
.length
-1;
int mid
= 0;
boolean isDescend
= true;
if(a
[right
] > a
[left
]){
isDescend
= false;
}
while(left
< right
){
mid
= left
+ (right
-left
)/2;
if(target
== a
[mid
]){
return mid
;
}else if(target
< a
[mid
]){
if(isDescend
) {
left
= mid
+ 1;
}else {
right
= mid
- 1;
}
}else{
if(isDescend
) {
right
= mid
- 1;
}else{
left
= mid
+ 1;
}
}
}
if(target
== a
[left
]){
return left
;
}else if(target
> a
[left
]){
return left
+1;
}
else{
return left
;
}
}
}
演示结果
