1 .山脈數(shù)組的巔峰索引

信息

我們把符合下列屬性的數(shù)組 A 稱作山脈：

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]
給定一個(gè)確定為山脈的數(shù)組，返回任何滿足 A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] 的 i 的值。

示例 1：

輸入：[0,1,0]
輸出：1
示例 2：

輸入：[0,2,1,0]
輸出：1

提示：

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定義的山脈

答案

class Solution(object):def peakIndexInMountainArray(self, A):""":type A: List[int]:rtype: int"""return A.index(max(A))

2.兩個(gè)數(shù)組的交集

信息

給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來(lái)計(jì)算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4]
說(shuō)明:

輸出結(jié)果中的每個(gè)元素一定是唯一的。
我們可以不考慮輸出結(jié)果的順序。

答案

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""dic = {}p=[]for num in nums1:if num not in dic:dic[num] = 0for num in nums2:if num in dic:p.append(num)del dic[num]return p

3. 二分查找

信息

有序的數(shù)組nums:

答案

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left ,right = 0, len(nums)-1while left <= right:mid=(left + right)/2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1 return -1

4 .在數(shù)組中是否存在兩個(gè)數(shù)，使其和等于target

信息

給定一個(gè)已按照升序排列 的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。

函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2。

說(shuō)明:

返回的下標(biāo)值（index1 和 index2）不是從零開始的。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。
示例:

輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 。

答案

class Solution(object):def twoSum(self, numbers, target):""":type numbers: List[int]:type target: int:rtype: List[int]"""low,high = 0,len(numbers)-1while(low < high):if (numbers[low] + numbers[high] == target):return [low+1, high+1]elif numbers[low] + numbers[high] <target:low = low + 1else:high = high - 1

5.搜索插入位置

信息

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。

示例 1:

輸入: [1,3,5,6], 5
輸出: 2
示例 2:

輸入: [1,3,5,6], 2
輸出: 1
示例 3:

輸入: [1,3,5,6], 7
輸出: 4
示例 4:

輸入: [1,3,5,6], 0
輸出: 0

答案

class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""low,high = 0,len(nums)while low <high:mid = low + (low+high)//2if nums[mid] > target:high=midelif nums[mid] <target:low=mid+1else:return midreturn low

6. 找到兩個(gè)數(shù)組的交集

信息

給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來(lái)計(jì)算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說(shuō)明：

輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。
我們可以不考慮輸出結(jié)果的順序。
進(jìn)階:

如果給定的數(shù)組已經(jīng)排好序呢？你將如何優(yōu)化你的算法？
如果 nums1 的大小比 nums2 小很多，哪種方法更優(yōu)？
如果 nums2 的元素存儲(chǔ)在磁盤上，磁盤內(nèi)存是有限的，并且你不能一次加載所有的元素到內(nèi)存中，你該怎么辦？

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的算法【二分查找】（数组）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。