題目詳情:
給定一(yi)個(ge) n 個(ge)元(yuan)素有序的(de)(升序)整型數組(zu) nums 和一(yi)個(ge)目(mu)標值 target ,寫一(yi)個(ge)函(han)數搜索 nums 中的(de) target,如果目(mu)標值存在返(fan)回(hui)下標,否則返(fan)回(hui) -1。
示例:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋(shi): 9 出現在 nums 中并且(qie)下標(biao)為 4
解題思路:
在每(mei)次循環中,我們(men)計算中間(jian)位(wei)置(zhi)的(de)下標 mid,并將中間(jian)元(yuan)素與目標值進行比較。如(ru)果它們(men)相等,則找到了目標值,返回中間(jian)下標。
如果(guo)中間元素小于目(mu)(mu)標值,則說明(ming)目(mu)(mu)標值應該在右半部分,我(wo)們(men)更新左(zuo)指針 left 為 mid + 1,縮小搜索范(fan)圍。
如果中間元素大于目標值(zhi),則說明目標值(zhi)應該在左半(ban)部(bu)分,我們(men)更(geng)新右指針 right 為 mid - 1,縮小(xiao)搜索范圍。
重復(fu)上述步(bu)驟,直到(dao)找到(dao)目標(biao)值或搜索范圍為空(kong)(即 left > right),此時返回 -1 表示沒有找到(dao)目標(biao)值。
代碼實現:
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid; // 找到目標值,返回下標
} else if (nums[mid] < target) {
left = mid + 1; // 目標值在右半部分,縮小搜索范圍
} else {
right = mid - 1; // 目標值在左半部分,縮小搜索范圍
}
}
return -1; // 沒有找到目標值,返回 -1
}
// 示例輸入
const nums = [-1, 0, 3, 5, 9, 12];
const target = 9;
// 調用函數并輸出結果
console.log(search(nums, target));