return -1;
}
if(end==(start+1)){
if(array[start]==value){
return start;
}else if(array[end]==value){
return end;
}
}else if(array[middle]==value){
return middle;
}else if(value>array[middle]){
return binarySearch(array,middle+1,end,value);
}else if(value
return binarySearch(array,start,middle-1,value);
}
return -1;
}
上述代碼稍加改變,就可以排序任意類型。如使用泛型,然后加上對Comparable接口的實現(xiàn),即可。
快速排序算法
二分搜索算法確實非?欤撬荒苡糜谝雅判驍(shù)組。如果數(shù)組未排序呢,該怎么辦呢?簡單,先用快速排序算法進行排序,然后再用二分搜索進行搜索。
先排序再搜索,要比匹配每一個元素快得多。搜索引擎,數(shù)據(jù)庫索引也都使用了對數(shù)據(jù)集合的排序技術(shù),這樣搜索數(shù)據(jù)才會快速。
理論:
最慢,也是最容易想到的排序算法是插入排序算法:
1, 遍歷數(shù)組,找出最小的元素,把它放到第一個元素。
2, 循環(huán)查找未排序的數(shù)組,直到整個數(shù)組排序。
這需要2個嵌套的循環(huán),意味著它的效率是O(n^2);
之所以插入排序的效率如此之地,是因為要找出整個數(shù)組中最小的數(shù)據(jù),需要遍歷整個數(shù)組的元素。
而插入排序聰明就聰明在它不查找整個數(shù)組最小、次小…的元素,而是每次僅僅把小于某個元素的值移到一邊,通過迭代最終自動實現(xiàn)排序。這就大大節(jié)約了排序所需的計算步驟。
相關(guān)推薦:北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |