🤵Author：今日說“法”

🏆主攻領域：算法分析與設計

📰個人主頁：今日說"法"的博客
📝系列專欄：NOWCODE系列

??前言

? ? ? ? 一位大佬曾經說過：程序=數據結構+算法??，數據結構相當于一套普遍適用的工具，算法相當于一套行之有效的解題方法和解題步驟。Dambisa Moyo 曾經說過：“種一顆樹最好的時間是十年前，其次是現在?！彼允昵皼]有刷題的朋友，現在跟著博主一起刷題吧。

工具介紹：數組

定義

數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。

結構

數組=一塊連續的存儲空間，我們假想數據下方有下標
?

優缺點

優點:查詢/查找/檢索其個下際上的元素時效事極高?？梢哉f是查詢效事最高的一個數據結構。

為什么檢索效事高?

第一:每一個元素的內存地址在空間存儲上是連續的。

第二：每一個元素類型相同，所以占用空間大小一樣。

第三:知道第一個元素內存地址，知道每一個元素占用空間的大小，又知道下標，所以通過一個數學表達式就可以計算出某個下標上元素的內存地址。直接通過內存地址定位元素，所以數組的檢索效事是最高的。

數組中存儲100個元責，或者存結100萬個元素，在元素查詢/檢索方面，效事是相同的。因為數組中元責查找的時候不會一個一個找，是通過數學表達式計算出來的。(算出一個內存地址，隨接定位的。)

缺點:

第一:由于為了保證數組中每個元素的內存的加連續，所以在數組上隨機制除或者增加元素的時候效事較紙，因為隨機增別元責會涉及到后面元素統一向前或者向后位移的操作。

第二:數組不能存能大數據最，為什么?

因為很難在內存空間上找到一塊特別大的連續的內存空間。

注意:對于數組中最后一個元素的增別，是沒有效事影啊的。

CODE Exercise：

One:二分查找-I

難度：????

時間限制：1秒

空間限制：256M

?

描述

請實現無重復數字的升序數組的二分查找

給定一個 元素升序的、無重復數字的整型數組 nums?和一個目標值 target?，寫一個函數搜索 nums?中的 target，如果目標值存在返回下標（下標從 0 開始），否則返回 -1

數據范圍：0≤len(nums)≤2×10^5?，?數組中任意值滿足 ∣val∣≤109

進階：時間復雜度 (logn)?，空間復雜度 O(1)

示例1

輸入：[-1,0,3,4,6,10,13,14],13

返回值：6

說明：13 出現在nums中并且下標為 6

示例2

輸入：[],3

返回值：-1

說明：nums為空，返回-1

示例3

輸入：[-1,0,3,4,6,10,13,14],2

返回值：-1

說明：2 不存在nums中因此返回 -1

備注：

數組元素長度在[0,10000]之間

數組每個元素都在?[-9999, 9999]之間。

Submit(python)

?

class Solution:def search(self , nums: List[int], target: int) -> int:# write code hereif len(nums)==0:return -1lenth_low=0lenth_high=len(nums)-1lenth_haf=(lenth_low+lenth_high)//2while lenth_low<=lenth_high:lenth_haf=(lenth_low+lenth_high)//2if target==nums[lenth_haf]:return lenth_hafif target>nums[lenth_haf]:lenth_low=lenth_haf+1if target<nums[lenth_haf]:lenth_high=lenth_haf-1return -1

Two:?二維數組中的查找

難度：??????

時間限制：1秒

空間限制：256M?

描述

在一個二維數組array中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

[

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]

給定 target?= 7，返回?true。

給定?target?=?3，返回?false。

數據范圍：矩陣的長寬滿足5?0≤n,m≤500?， 矩陣中的值滿足 0≤val≤10^9
進階：空間復雜度?O(1) ，時間復雜度?O(n+m)

?

示例1

輸入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：true

說明：存在7，返回true

示例2

輸入：1,[[2]]

返回值：false

示例3

輸入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：false

說明：不存在3，返回false

Submit(python)?

class Solution:def Find(self , target: int, array: List[List[int]]) -> bool:# 利用list.count()查找數組中每一行的元素# 用len()取得行數for i in range(len(array)):if array[i].count(target):return True return False

?

Three:?尋找峰值

難度：??????

時間限制：1秒

空間限制：256M

描述

給定一個長度為n的數組nums，請你找到峰值并返回其索引。數組可能包含多個峰值，在這種情況下，返回任何一個所在位置即可。

1.峰值元素是指其值嚴格大于左右相鄰值的元素。嚴格大于即不能有等于

2.假設?nums[-1] = nums[n] =?∞

3.對于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的時間復雜度實現此問題嗎？

?

如輸入[2,4,1,2,7,8,4]時，會形成兩個山峰，一個是索引為1，峰值為4的山峰，另一個是索引為5，峰值為8的山峰，如下圖所示：

?

?

示例1

輸入：[2,4,1,2,7,8,4]

返回值：1

說明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以

示例2

輸入：[1,2,3,1]

返回值：2

說明：3 是峰值元素，返回其索引 2

Submit(python)?

?

class Solution:def findPeakElement(self , nums: List[int]) -> int:# write code herefor i in range(1,len(nums)-1):if nums[i]>nums[i-1] and nums[i]>nums[i+1]:return iif max(nums)==nums[-1]:return len(nums) -1elif max(nums) == nums[0]:return 0

🔥結語

? ? ? ? ???冰凍三尺非一日之寒??，只刷一兩天刷法可成不了編程界的耶路撒冷，千里之行始于足下，所以還是得堅持刷題阿，每天記得要上機喲！！！

總結

以上是生活随笔為你收集整理的【NOWCODE SEVEN】:二分查找/排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。