leetcode 33 搜索旋轉(zhuǎn)排序數(shù)組
第一次題解
思路：將數(shù)組分為兩份星掰，左邊的數(shù)組可能是有序的可能是無(wú)須的叫倍，通過(guò)一個(gè)while找出[left, mid] 是有序的，這樣能找到旋轉(zhuǎn)位置解愤，再根據(jù)二分搜索法找出taget值冈绊。
自我點(diǎn)評(píng)：
- 時(shí)間復(fù)雜度為log(n)級(jí)別
- 應(yīng)多用注釋標(biāo)記出邊界點(diǎn)范圍節(jié)省調(diào)試的時(shí)間侠鳄。
- 局限于找出旋轉(zhuǎn)位置
- 代碼較多，理解起來(lái)困難
- 以后使用low死宣，hight單詞代替 left伟恶，right。
class Solution {
fun search(nums: IntArray, target: Int): Int {
if (nums.isEmpty()) return -1
return searchTag(nums, 0, nums.lastIndex, target)
}
private fun searchTag(nums: IntArray, left: Int, right: Int, target: Int): Int {
var mRight = right
var mid = (left + mRight) / 2 // 可優(yōu)化 (right - left) / 2 + left
// [left, mRight] 有序毅该，查找Tga值
if (nums[left] <= nums[mRight]) return binarySearch(nums, left, mRight, target)
// 找出 [left, mid] 是有序的
while (nums[mid] < nums[left]) {
mRight = mid
mid = (left + mRight) / 2 // 可優(yōu)化 (right - left) / 2 + left
}
// target 存在 [let, mid] 之間
if (target >= nums[left] && target <= nums[mid]) return binarySearch(nums, left, mid, target)
// [mid+1, right] 從新搜索
return searchTag(nums, mid + 1, right, target)
}
private fun binarySearch(nums: IntArray, left: Int, right: Int, target: Int): Int {
if (left > right) return -1
val mid = (right - left) / 2 + left // 可優(yōu)化 (right - left) / 2 + left
return when {
nums[mid] == target -> mid
nums[mid] < target -> binarySearch(nums, mid + 1, right, target)
else -> binarySearch(nums, left, mid - 1, target)
}
}
}
優(yōu)雅解法
思路：如果中間的數(shù)小于最右邊的數(shù)博秫，則右半段是有序的，若中間數(shù)大于最右邊數(shù)眶掌，則左半段是有序的挡育，我們只要在有序的半段里用首尾兩個(gè)數(shù)組來(lái)判斷目標(biāo)值是否在這一區(qū)域內(nèi)，這樣就可以確定保留哪半邊了
class Solution {
fun search(nums: IntArray, target: Int): Int {
if (nums.isEmpty()) return -1
return searchTag(nums, 0, nums.lastIndex, target)
}
private fun searchTag(nums: IntArray, left: Int, right: Int, target: Int): Int {
var low = left
var hight = right
while (low <= hight) {
val mid = (low + hight) / 2
if (target == nums[mid]) return mid
if (nums[mid] < nums[hight]) {// [mid, right]
if (nums[mid]< target && target <= nums[hight]) low = mid + 1 // num[mid] < target <= num[right]
else hight = mid - 1
}else {
if (nums[low] <= target && target < nums[mid]) hight = mid - 1 // num[right] <= target < num[mid]
else low = mid + 1
}
}
return -1
}
}
