今天突然想創(chuàng)建一個文集，做一些公司筆試題小染，原因如下：
1芋绸、想鍛煉自己的變成能力耙厚。
2、逼迫自己刷題，以應(yīng)對找工作時的筆試攒暇。
今天是第一題卿城，就先來個簡單的程序园蝠，以后會持續(xù)堅持电湘。
題目：
對于一個有序數(shù)組，我們通常采用二分查找的方式來定位某一元素筐带，請編寫二分查找的算法今穿，在數(shù)組中查找指定元素。
給定一個整數(shù)數(shù)組A及它的大小n伦籍，同時給定要查找的元素val蓝晒，請返回它在數(shù)組中的位置(從0開始)，若不存在該元素帖鸦，返回-1芝薇。若該元素出現(xiàn)多次，請返回第一次出現(xiàn)的位置富蓄。
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
}
}
分析：
看到這道題目剩燥，第一感覺就是簡單，之前都是通過遞歸實現(xiàn)立倍，這次同樣想用遞歸來進(jìn)行實現(xiàn)灭红，但是細(xì)看后發(fā)現(xiàn)題目提供的方法傳遞的參數(shù)個數(shù)即類型不能使用遞歸，此時就想換循環(huán)來實現(xiàn)口注，到這里我就已經(jīng)被自己看到的和自己的想法給限制類思維变擒，因為之后想到，雖然他給了方法聲明寝志，沒說不可以再次聲明自己的方法娇斑。
然后就迅速使用遞歸實現(xiàn)了程序。
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]測試本應(yīng)返回0苦丁，結(jié)果卻返回1。當(dāng)時一臉懵逼物臂，在從讀題目旺拉，知道看到最后一句話“若該元素出現(xiàn)多次产上，請返回第一次出現(xiàn)的位置”。這句話很容易理解蛾狗，在程序中只需要每次判斷start下標(biāo)對應(yīng)的value是否和目標(biāo)value相等即可晋涣，所以在fun()方法中添加以下代碼。
if(A[start] == val){
return start;
}
提交結(jié)果正確沉桌，測試通過谢鹊。
參考答案：
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赌莺、不是你覺得簡單就真的簡單冰抢，往往細(xì)節(jié)決定成敗。
