題目描述
給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為?
O(log n)?的算法。示例 1:
輸入: nums = [1,3,5,6], target = 5 輸出: 2示例?2:
輸入: nums = [1,3,5,6], target = 2 輸出: 1示例 3:
輸入: nums = [1,3,5,6], target = 7 輸出: 4
解題思路
使用二分查找尋找target，如果target存在就返回它在數組中的下標，如果它不存在就返回它的插入位置，我們只需要不停的對比mid的元素大小和target的關系，如果當前mid對應的元素已經大于target，就令right = mid? - 1，往更小的區間找；如果當前mid對應的元素小于target,就令left = mid + 1,?往更大的區間找；如果當前mid對應元素已經和target相等，則直接返回mid；當退出循環后，說明target不在數組中，但當前left指向的位置即為要插入的位置
代碼實現
class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {return mid;}}return left;}
}
)
)
)
