LeetCode資料結構_二分搜索(Binary Search)
通常假設搜尋對象是一個有序的數列。這種搜尋算法通過將數列分成兩半，並比較中間元素與目標值的大小來迅速定位目標值的位置。 固定左右邊界，用中間值與目標值判斷大小，根據情況收縮左邊界或者右邊界即可。 https://ninagirl1998.medium.com/leetcode-33-search-in-rotated-sorted-array-da1df6111576 https://www.guru99.com/binary-search.html 假設我們有一個有序的整數陣列：[2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]，現在我們想要找到目標值 23 是否在這個陣列中，如果在，我們還希望知道它的索引位置。 傳統的線性搜索方法是從陣列的第一個元素開始，逐一比較直到找到目標值或者確定目標值不存在。但是這種方法的時間複雜度是O(n)，當數列很大時，效率較低。 運用二分搜索的方法 Step1. 首先指定搜索範圍，即整個數列。左邊界設置為0，右邊界設置為陣列長度減1：left = 0，right = 10（假設陣列索引從0開始計算）。 Step2. 接下來，我們計算中間元素的索引：mid = (left + right) / 2 = 5。 Step3.比較中間元素23與目標值23的大小。[2, 5, 8, 12, 16, 23 , 38, 45, 56, 72, 91] 由於它們相等，我們已經找到目標值，並且其索引為5。 Step4.搜索結束。 透過二分搜索，我們只用了幾次比較就找到了目標值的位置。這種方法的時間複雜度是O(log n)，比線性搜索的O(n) 效率更高。當數列很大時，二分搜索的優勢就會體現出來。 在有序數列中，二分搜索的平均時間複雜度是O(log n)，非常高效。特別在大數據量下，相比於線性搜索的O(n)，速度快得多。 二分搜索是一種高效的搜尋算法，特別適用於有序數列。它通過將搜索範圍分為兩半來迅速定位目標值，從而大大節省了搜索的時間。 69. Sqrt(x)(Easy) https://leetcode.com/problems/sqrtx/ 題目描述：計算非負整數 x 的平方根。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
