package search;
public class BinarySearch{
public static int rank(int key, int[] a) {
return rank(key, a, 0, a.length - 1);
}
/**
* 根據(jù)首尾元素的比較結(jié)果判斷數(shù)組的升降序
* @param key
* @param a
* @param lo
* @param hi
* @return
*/
public static int rank(int key, int[] a, int lo, int hi) {
return a[lo] < a[hi] ? rankAsc(key, a, lo, hi) : rankDesc(key, a, lo, hi);
}
/**
* 對(duì)升序數(shù)組進(jìn)行查找
* @param key
* @param a
* @param lo
* @param hi
* @return
*/
public static int rankAsc(int key, int[] a, int lo, int hi) {
while(lo <= hi){
int mid = (lo + hi) / 2;
if(key < a[mid]) hi = mid - 1;
else if(key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
/**
* 對(duì)降序數(shù)組進(jìn)行查找
* @param key
* @param a
* @param lo
* @param hi
* @return
*/
public static int rankDesc(int key, int[] a, int lo, int hi) {
while(lo <= hi){
int mid = (lo + hi) / 2;
if(key > a[mid]) hi = mid - 1;
else if(key < a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
/**
* 返回匹配鍵的最小索引
* @param key
* @param a
* @return
*/
public static int rankFirstIndex(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
int index = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(key < a[mid]) hi = mid - 1;
else if(key > a[mid]) lo = mid + 1;
else{index = mid; break;}
}
while(index > 0){
if(a[index-1] != a[index]) break;
else index--;
}
return index;
}
}
1.2.9 BinarySearch
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)公给，“玉大人借帘，你說(shuō)我怎么就攤上這事√暑恚” “怎么了肺然？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀(guān)的道長(zhǎng)匣沼。 經(jīng)常有香客問(wèn)我狰挡，道長(zhǎng)捂龄，這世上最難降的妖魔是什么释涛？ 我笑而不...
- 正文 為了忘掉前任，我火速辦了婚禮倦沧，結(jié)果婚禮上唇撬，老公的妹妹穿的比我還像新娘。我一直安慰自己展融，他們只是感情好窖认，可當(dāng)我...
- 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著告希，像睡著了一般扑浸。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上燕偶，一...
- 那天喝噪，我揣著相機(jī)與錄音，去河邊找鬼指么。 笑死酝惧，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的伯诬。 我是一名探鬼主播晚唇，決...
- 文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼盗似！你這毒婦竟也來(lái)了哩陕？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎悍及，沒(méi)想到半個(gè)月后葵礼，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡并鸵，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年鸳粉，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片园担。...
- 正文 年R本政府宣布咏闪，位于F島的核電站曙搬，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏鸽嫂。R本人自食惡果不足惜纵装，卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望据某。 院中可真熱鬧橡娄，春花似錦、人聲如沸癣籽。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)筷狼。三九已至瓶籽，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間埂材，已是汗流浹背塑顺。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長(zhǎng)得像寡喝，于是被迫代替她去往敵國(guó)和親糙俗。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 每年到這個(gè)時(shí)候翰舌，身邊就會(huì)有很多人開(kāi)始咳嗽、咳痰冬骚、流鼻涕椅贱、打噴嚏的，有些是感冒只冻、有些是哮喘庇麦、有些是氣管炎，有些的鼻炎...
- 一般來(lái)說(shuō)入桂，喜歡站立的人奄薇，比喜歡躺著或或坐著的人，身材更好抗愁。與躺著的姿勢(shì)相比馁蒂，站姿所消耗的能量要多出10%。而單腿站...
- 一、 正在家里看電視胚膊，老媽接了個(gè)電話(huà)嗜湃，奇怪的眼神看著我：“找你的±窖冢”我也是一臉的好奇购披，老媽說(shuō)是個(gè)男生，是我同學(xué)肩榕。 ...
