二分查找（easy）
更好的閱讀體驗應該是：
- 審題-思考
- 答題
- 整理-歸納
一、題目
LeetCode：704.二分查找
給定一個 n 個元素有序的（升序）整型陣列 nums 和一個目標值 target ，寫一個函式搜索 nums 中的 target，如果目標值存在回傳下標，否則回傳 -1，
示例:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下標為 4
你可以假設 nums 中的所有元素是不重復的，
二、二分法解題
二分查找是一種基于比較目標值和陣列中間元素的教科書式演算法，
- 如果目標值等于中間元素，則找到目標值，
- 如果目標值較小，繼續在左側搜索，
- 如果目標值較大，則繼續在右側搜索，
時間復雜度：O(logN)，
空間復雜度：O(1)，
模版 I
- 確定初始的左右邊界:
left: 0right: nums.length-1mid: (left + right) >> 1
- 如果中間元素值
nums[mid]< target：證明中間值左側包括中間值都不符合要求，可以直接排除，left = mid + 1 - 如果中間元素值
nums[mid]：證明中間值右側包括中間值都不符合要求，可以直接排除，right = mid - 1 - 如果中間元素值
nums[mid]= target：直接回傳mid的下標 - 重新定義了左右邊界，也需要重新計算中間值，我們需要繼續進行范圍的排除
- 定義搜索的條件，應該是搜索區間都不為空，即
left <= right
Javasciprt 代碼
var search = function(nums, target) {
let left = 0; // 初始左邊界
let right = nums.length - 1; // 初始右邊界
// 如果left > right 證明整個陣列結束了仍沒有找到目標值
while (left <= right) {
let mid = left + Math.floor((right - left) / 2); //防止溢位
if (target === nums[mid]) {
return mid;
} else if (target > nums[mid]) {
// 目標值大于中值，則中間左側可以拋棄了
left = mid + 1;
} else {
// 目標值小于中值，則中間右側可以拋棄了
right = mid - 1;
}
}
return -1;
};
三、寫在最后
上面的代碼就是二分法模板 I，看過我的二分法總結的同學應該知道，憑借這套模版以及對應的分析，類似的問題應該難不住你了，
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵，
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- Github：JavaScript 版 LeetCode 題解
- 在線版：前端進階筆記
- CSDN博客匯總
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/232063.html
標籤：其他
上一篇：女朋友生日? HTML+css3+js 實作炫酷3D相冊 (含背景音樂)
下一篇：請問大家，一個點擊洗掉元素的問題