二分查找兩種實(shí)現(xiàn)，附詳細(xì)注釋

二分查找問題描述

給定一個??個元素有序的（升序）整型數(shù)組? 和一個目標(biāo)值? ?，寫一個函數(shù)搜索??中的 ，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1。

示例 1:

輸入:?nums?=?[-1,0,3,5,9,12],?target?=?9
輸出:?4
解釋:?9?出現(xiàn)在?nums?中并且下標(biāo)為?4

示例?2:

輸入:?nums?=?[-1,0,3,5,9,12],?target?=?2
輸出:?-1
解釋:?2?不存在?nums?中因此返回?-1

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/binary-search

2 解法1：左閉右開

使用區(qū)間：左閉右開，詳細(xì)思路見文中代碼注釋：

class?Solution(object):
????def?search(self,?nums,?target):
????????#?剛開始的取值區(qū)間：[0,len(nums)?)
????????left,right=0,len(nums)
????????while?right?-?left?>?1:
????????????mid?=?(left+right)?//2
????????????#?nums[0]<=...
????????????if?nums[mid]?<=?target:
????????????????#?遍歷后區(qū)間改變?yōu)椋篬mid,right)
????????????????left?=?mid
????????????else:
????????????????#?nums[right-1]...>=nums[mid+1]>=nums[mid]?>?target
????????????????#?區(qū)間調(diào)整為：[left,right)
????????????????right?=?mid
????????#?迭代結(jié)束后
????????#?right-left=1，區(qū)間為[left,?right=left+1)????????
????????#?即nums[left]就是二分后逼近的點(diǎn)
????????#?判斷nums[left]是否等于target即可
????????return?left?if?nums[left]?==?target?else?-1

2 解法2：左閉右閉

class?Solution(object):
????def?search(self,?nums,?target):
????????#?左右都是閉合區(qū)間的寫法
????????#?剛開始的取值區(qū)間：[0,len(nums)-1]
????????left,right=0,len(nums)-1
????????while?left?<=?right:
????????????mid?=?(left+right)?//2
????????????if?nums[mid]?==?target:
????????????????return?mid
????????????#?nums[0]<=...
????????????elif?nums[mid]?????????????????#?遍歷后區(qū)間改變?yōu)椋篬mid+1,right]
????????????????left?=?mid?+?1?
????????????else:
????????????????#?nums[right-1]...>=nums[mid+1]>=nums[mid]?>?target
????????????????#?區(qū)間調(diào)整為：[left,mid-1]
????????????????right?=?mid-1
????????#?迭代結(jié)束后
????????# left - right = 1，此時區(qū)間[left,right]?=?[left,left-1]變?yōu)榭眨?/span>
????????#?所以返回?-1
????????return?-1

二分查找，是最基本的分支法的一個應(yīng)用，面試中被問道的頻率很高，同時邊界取值特別容易出錯，所以單獨(dú)寫為一篇文章，帶有詳細(xì)的注釋，希望將來面試能幫助到你一點(diǎn)。覺得還可以，可否點(diǎn)個贊。

算法參考書

如果你的英文還不錯，可以學(xué)習(xí)下面這本算法分析書，幾乎從0開始教會你算法的基本概念，數(shù)據(jù)結(jié)構(gòu)，然后基本的算法設(shè)計(jì)技術(shù)，常用到的比如分治、貪心、動歸、回溯、分治定界、隨機(jī)算法等。

掌握這300頁，不管你是軟件設(shè)計(jì)、算法設(shè)計(jì)、數(shù)據(jù)分析、爬蟲等，基本的算法思想算是掌握了，大家加油！

若有需求，加我微信，備注 算法