今天突然想创建一个文集，做一些公司笔试题，原因如下：
1、想锻炼自己的变成能力。
2、逼迫自己刷题，以应对找工作时的笔试。
今天是第一题，就先来个简单的程序，以后会持续坚持。
题目：
对于一个有序数组，我们通常采用二分查找的方式来定位某一元素，请编写二分查找的算法，在数组中查找指定元素。
给定一个整数数组A及它的大小n，同时给定要查找的元素val，请返回它在数组中的位置(从0开始)，若不存在该元素，返回-1。若该元素出现多次，请返回第一次出现的位置。
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
}
}
分析：
看到这道题目，第一感觉就是简单，之前都是通过递归实现，这次同样想用递归来进行实现，但是细看后发现题目提供的方法传递的参数个数即类型不能使用递归，此时就想换循环来实现，到这里我就已经被自己看到的和自己的想法给限制类思维，因为之后想到，虽然他给了方法声明，没说不可以再次声明自己的方法。
然后就迅速使用递归实现了程序。
public class BinarySearch {
public static void main(String[] args) {
int[] a = new int[]{1,1,4,5,6};
int po = new BinarySearch().getPos(a, a.length, 1);
System.out.println(po);
}
public int getPos(int[] A, int n, int val) {
return fun(A, val, 0, n-1);
}
public int fun(int[] A, int val, int start, int end){
if(start > end){
return -1;
}
int middle = (start + end)/2;
if(val > A[middle]){
start = middle + 1;
return fun(A, val, start, end);
}
if(val < A[middle]){
end = middle - 1;
return fun(A, val, start, end);
}
if(val == A[middle]) {
return middle;
}
return -1;
}
}
提交程序，然后提交报错。。。说是使用[1,1,2]测试本应返回0，结果却返回1。当时一脸懵逼，在从读题目，知道看到最后一句话“若该元素出现多次，请返回第一次出现的位置”。这句话很容易理解，在程序中只需要每次判断start下标对应的value是否和目标value相等即可，所以在fun()方法中添加以下代码。
if(A[start] == val){
return start;
}
提交结果正确，测试通过。
参考答案：
public class BinarySearch {
public static void main(String[] args) {
int[] a = new int[]{1,1,4,5,6};
int po = new BinarySearch().getPos(a, a.length, 1);
System.out.println(po);
}
public int getPos(int[] A, int n, int val) {
return fun(A, val, 0, n-1);
}
public int fun(int[] A, int val, int start, int end){
if(start > end){
return -1;
}
if(A[start] == val){
return start;
}
int middle = (start + end)/2;
if(val > A[middle]){
start = middle + 1;
return fun(A, val, start, end);
}
if(val < A[middle]){
end = middle - 1;
return fun(A, val, start, end);
}
if(val == A[middle]) {
return middle;
}
return -1;
}
}
感想：
1、不要别人没有限制你的思维，你自己却给自己画一个小圈。
2、不是你觉得简单就真的简单，往往细节决定成败。
网友评论