題目：
給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，
你可以假設陣列中無重復元素，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-insert-position/
示例一：
輸入: [1,3,5,6], 5
輸出: 2
示例二：
輸入: [1,3,5,6], 2
輸出: 1
示例三：
輸入: [1,3,5,6], 7
輸出: 4
示例四：
輸入: [1,3,5,6], 0
輸出: 0
思路一：
回圈遍歷陣列，將陣列元素取出對比，題目中提到順序，從示例中可看出為從小到大，即分為四種情況，目標數比第一個陣列中的元素都小，直接回傳"0";目標數比陣列中所有元素都大，回傳陣列長度作為目標函式下標;目標數在陣列中存在，將陣列對應的下標取出；目標數在陣列中不存在，但又在陣列的范圍內，遇到比目標數大的數，將目標數放在這個數前面，即回傳這個數的下標，
代碼演示：
class Solution {
public int searchInsert(int[] nums, int target) {
//回圈遍歷取出陣列元素，
for (int i = 0; i <= nums.length; i++) {
//當陣列元素大于目標值時，目標值代替原本陣列的位置,相等則回傳對應下標
if (nums[i] >= target) {
return i;
} else if (nums[nums.length - 1] < target) {
return nums.length;
}
}
return 0;
}
}
檢查結果：
思路二：
使用二分法，在排序陣列中遇到求目標值的，第一反應就是二分法查找目標值，
- 設立左下標和右下標，設立中間值
- 根據中間值在陣列中的數值，與目標值比較相等回傳中間值，陣列值小于目標值左下標右移，陣列值大于目標值，右指標左移
- 如果沒有查找到對應陣列的值，則回傳left，left為插入位置
代碼演示：
class Solution {
public int searchInsert(int[] nums, int target) {
//設立左指標和中間指標
int left = 0, mid;
//設立右指標
int right = nums.length - 1;
//當左指標超過右指標時結束運行
while (left <= right) {
//相加除2獲取中間值，相減除2獲取長度的一半，四舍五入向下取整
mid = (int) (right + left) / 2;
//當中間值等于目標值時，回傳中間值
if (nums[mid] == target) {
return mid;
//中間值大于目標值，右指標移動
} else if (nums[mid] > target) {
right = mid - 1;
//中間值小于目標值，左指標移動
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return left;
}
}
檢測結果：
感謝你的閱讀，不足之處歡迎批評指正！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/275458.html
標籤：java
上一篇：Java 方法 遞回使用及練習