定義
從一個簡單問題說起
給定一個排序并不存在重復元素的數(shù)組: [1,2,5,7,8,9,13], 查找8的位置
暴力解法: 遍歷整個數(shù)組, 找到與給定值相同的元素, 返回下標, 時間復雜度O(n)
另一種解法:
- 我們可以先取數(shù)組中間位置的值, 看中間位置的值和目標值的大小, 假如中間位置的值大于目標值, 則說明目標值處于數(shù)組的中間位置的左半部分, 假如中間位置的值小于目標值, 則說明目標值處于數(shù)組中間位置的右半部分
- 這里我們假設(shè)數(shù)組中間位置的值大于目標值, 則說明目標值處于數(shù)組中間值的左半部分, 那么右半部分我們就不需要再去查找了
- 對于中間值的左半部分我們繼續(xù)取中間位置的值, 像上面那樣我們繼續(xù)判斷中間位置的值的大小, 大于目標值我們?nèi)∽蟀氩糠? 小于目標值我們?nèi)∮野氩糠?/li>
- 按照上面每次去一半的方法一直分下去, 直到數(shù)組中的某個位置值與目標值相等, 返回該位置
時間復雜度: 由于我們每次分割都會少掉一半, 所以時間復雜度為O(logn)
二分搜索
上面這種每次取一半搜索的方法就是二分搜索
二分搜索注意事項
- 對輸入做異常處理: 數(shù)組為空或者數(shù)組長度為0
- mid = start + (end - start) / 2 這種表示方法可以防止兩個整型值相加時溢出
- 使用迭代而不是遞歸進行二分查找, 因為工程中遞歸寫法存在潛在溢出的可能
- while終至條件: start + 1 < end而不是start <= end, start == end時可能出現(xiàn)死循環(huán)
- 迭代終至時target應為start或者end中的一個募壕。循環(huán)終至條件有兩個, 具體應看是找到第一個還是最后一個而定
function binarySearch(arr, target) {
if (arr.length < 1) {
return -1
}
let start = 0
let end = arr.length - 1
while (start + 1 < end) {
let mid = Math.floor(start + (end - start) / 2)
if (arr[mid] >= target) {
end = mid
}else if (arr[mid] < target) {
start = mid
}
}
if (arr[start] === target) {
return start
}
if (arr[end] === target) {
return end
}
return -1
}
例題
搜索插入位置
給定一個排序數(shù)組和一個目標值, 如果在數(shù)組中找到了目標值則返回索引。
如果沒有, 返回到它將會被按順序插入的位置差油。
你可以假設(shè)在數(shù)組中無重復元素
case1:
輸入: [1,3,5,6], 5 輸出: 2
case2：
輸入: [1,3,5,6], 2 輸出: 1
case3:
輸入: [1,3,5,6], 7 輸出: 4
case4:
輸入: [1,3,5,6], 0 輸出: 0
分析:
- 在目標值是數(shù)組中的數(shù)時, 很明顯這就是標準的二分搜索的題
- 在目標值不是數(shù)組中的數(shù)時, 情況分三種情況:
- 目標值在數(shù)組中某兩個數(shù)大小之間, 上面題的case2就是這種情況, 這種情況下, 目標值的大小一定是處在數(shù)組某相鄰兩個數(shù)之間, 換句話說也就是目標值永遠插入在start+1的位置
- 目標值比數(shù)組起始位置數(shù)還小, case4, 這種情況永遠返回0
- 目標值比數(shù)組最后一位的值還大. case3, 此時永遠返回arr.length + 1
function searchInsert(arr, target) {
if (arr.length < 1) {
return 0
}
let start = 0
let end = arr.length - 1
while (start + 1 < end) {
let mid = Math.floor(start + (end - start) / 2)
if (arr[mid] < target) {
start = mid
} else {
end = mid
}
}
if (arr[start] === target) {
return start
}
if (arr[end] === target) {
return end
}
if (target > arr[end]) {
return end + 1
}
if (target < arr[start]) {
return 0
}
return start + 1
}
搜索二維矩陣
編寫一個高效的算法來搜索m*n矩陣中的一個目標值。
該矩陣具有以下特性:
每行中的整數(shù)從左向右排序米死。
每行的第一個數(shù)大于前一行的最后一個整數(shù)莱找。
例如:
以下矩陣:
1???2???3???4
5???6???7???8
11 13 15 17
56 78 89 98
給定一個目標值3, 返回下標
分析:
- 由于每一行第一個數(shù)都比前一行最后一個數(shù)大, 所有這個矩陣轉(zhuǎn)換成一維數(shù)組的話, 是一個排好序的一維數(shù)組, 這個問題就可以轉(zhuǎn)換成一維數(shù)組搜索, 也就是最基本的二維數(shù)組問題
- 矩陣每一行4個元素, 第二行第一個matrix[1][0]轉(zhuǎn)換成一維數(shù)組時下標為1 * 4 + 0 = 4
矩陣第三行第二個matrix[2][1]轉(zhuǎn)換成一維數(shù)組時下標為 2 * 4 + 1 = 9
以此類推, matrix[n][m]轉(zhuǎn)換成一維數(shù)組時下標為n * 4 + m
一維數(shù)組arr[n]轉(zhuǎn)換成每組有m個數(shù)的martix時下標為matrix[n/m][n%m]
function binarySearch(matrix, target) {
if (matrix.length < 1 || matrix[0].length < 1) {
return -1
}
let start = 0
let end = matrix.length * matrix[0].length - 1
while (start + 1 < end) {
let mid = Math.floor(start + (end - start) / 2)
if (matrix[Math.floor(mid / matrix[0].length)][mid % matrix[0].length] < target) {
start = mid
} else {
end = mid
}
}
if (matrix[Math.floor(start / matrix[0].length)][start % matrix[0].length] === target) {
return [Math.floor(start / matrix[0].length), start % matrix[0].length]
}
if (matrix[Math.floor(end / matrix[0].length)][end % matrix[0].length] === target) {
return [Math.floor(end / matrix[0].length), end % matrix[0].length]
}
return -1
}
求整數(shù)的平方根
給定一個整數(shù), 返回它的平方根, 平方根不是整數(shù)的, 向下取整
例如:
輸入: 25 輸出: 5
輸入: 0 輸出: 0
輸入: 9 輸出: 3
輸入: 7 輸出: 2
分析:
這道題可以用二分搜索來做
- 取0到n中間的數(shù)m
- m的平方大于n的話說明, n的平方根在0到m之間
- 去0到m中間的值, 繼續(xù)平方, 如果大于n, 說明n的平方根在0到m/2之間, 如果小于m, 說明在m/2到m之間
- 依次類推, 直到找到結(jié)果, 如果分到?jīng)]辦法再分下去還沒有找到結(jié)果, 則返回最后一次取值范圍的左邊界
function mySqrt(n) {
if (n === 0) {
return 0
}else if (n < 0) {
return 'error'
}
let start = 0
let end = n
while (start + 1 < end) {
let mid = Math.floor(start + (end - start) / 2)
if (mid * mid < n) {
start = mid
} else {
end = mid
}
}
if (end === n / end) {
return end
}
return start
}
