一、題目地址
https://www.nowcoder.com/practice/7bc4a1c7c371425d9faa9d1b511fe193?tpId=117
二、具體代碼
/**
* 二分查找
* @param n int整型 陣列長度
* @param v int整型 查找值
* @param a int整型一維陣列 有序陣列
* @return int整型
*/
function upper_bound_( n , v , a ) {
//1、直接先考慮特殊情況：第一個大于等于目標值的數的位置，1號下標值為0，故輸出0 + 1 = 1，即1
if(a[0] >= v) {
return 1;
}
//2、下面是進行二分查找的步驟
let left = 0;
let right = n - 1;
while(left <= right) {
let mid = Math.floor((left + right) / 2);
//多一個等于判斷條件，是方便自己理解，但是時間復雜度同樣變高，所以做法僅供參考，
if(v === a[mid]) {
/*
加個while回圈的目的：
(1)當mid下標值對應的值等于目標值v時；
(2)該回圈是為了判斷：前面mid-1下標值對應的值是否同時也等于目標值v;
(3)如果等于，則mid下標值向前移動一位;
(4)直到mid下標值對應值的前一位值，不等于目標值v時，則跳出回圈;
(5)最后直接回傳mid + 1;
*/
while(mid != 0 && a[mid - 1] === a[mid]) mid--;
return mid + 1;
} else if(v < a[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
//3、如果沒找到，直接回傳題目要求中的n + 1
return n + 1;
}
module.exports = {
upper_bound_ : upper_bound_
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/292511.html
標籤：其他
上一篇：jquery簡單學習
下一篇：webpack學習整理（基礎）