704.二分查找
給定一個 n 個元素有序的（升序）整型陣列 nums 和一個目標值 target ，寫一個函式搜索 nums 中的 target，如果目標值存在回傳下標，否則回傳 -1，
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下標為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此回傳 -1
提示：
- 你可以假設
nums中的所有元素是不重復的， n將在[1, 10000]之間，nums的每個元素都將在[-9999, 9999]之間，
class Solution {
public int search(int[] nums, int target) {
int l=0;
int r=nums.length-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]<target){
l=mid+1;
}else if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]==target){
return mid;
}
}
return -1;
}
}
反思
該題自以為已經熟練掌握，但是在寫的時候還是卡住我了，
第一是對于目標值和中間元素的比較，我直接使用的是mid與target值的比較，實際應該是用nums陣列對應mid下標的值與target對比，
第二是關于邊界元素的確定，在比較target>nums[mid]時，我錯誤的將邊界元素寫成了r=mid-1.實際上在紙上一畫便知，邊界元素應該是：取陣列mid右邊的元素，所以應該改變l的取值，l=mid+1；同理tareget<nums[mid]時，應該寫成r=mid-1，
278. 第一個錯誤的版本
你是產品經理，目前正在帶領一個團隊開發新的產品，不幸的是，你的產品的最新版本沒有通過質量檢測，由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的，
假設你有 n 個版本 [1, 2, ..., n]，你想找出導致之后所有版本出錯的第一個錯誤的版本，
你可以通過呼叫 bool isBadVersion(version) 介面來判斷版本號 version 是否在單元測驗中出錯，實作一個函式來查找第一個錯誤的版本，你應該盡量減少對呼叫 API 的次數，
示例 1：
輸入：n = 5, bad = 4
輸出：4
解釋：
呼叫 isBadVersion(3) -> false
呼叫 isBadVersion(5) -> true
呼叫 isBadVersion(4) -> true
所以，4 是第一個錯誤的版本，
示例 2：
輸入：n = 1, bad = 1
輸出：1
提示：
1 <= bad <= n <= 231 - 1
思路
同樣這道題是利用二分法來做，給定一個n長度的版本，需要找到出錯的第一個版本，那么利用二分，當呼叫isBadVersion時，若回傳true，則應該向左側繼續查找；若回傳false，則證明出錯的在右側，應像右側查找
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int l=0;
int r=n;
while(l<r){
int mid=l+(r-l)/2;
if(isBadVersion(mid)){
r=mid;
}else{
l=mid+1;
}
}
return r;
}
}
反思
思路很好想到，但這道題不同于上一道題的二分判斷，該題在于設定了l=0，r=n，那么當你選擇中間值時，mid=l+(r-l)/2；判斷mid處的版本是否為出錯版本，若是出錯版本，則應該往左側查，這樣就令r=mid即可，因為你不確定這個mid處的版本是否就是出錯的第一個版本，所以要把右邊界設定為mid；那么同理既然已經判斷過mid處了，則如果判斷回傳false，則向右側查時，左邊界應該為mid+1.
35. 搜索插入位置
給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，
請必須使用時間復雜度為 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
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums為 無重復元素 的 升序 排列陣列-104 <= target <= 104
class Solution {
public int searchInsert(int[] nums, int target) {
int l=0;
int r=nums.length-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]<target){
l=mid+1;
}else if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]==target){
return mid;
}
}
return l;
}
}
反思
該題的關鍵在于當你找的target值不在陣列時，應該插到哪個位置，
依照二分法進行演草，可以知道，如果不在陣列，那么每次的遞回遍歷總是要將target值插入l位置處，
例如 1 2 4 5 6 target=3時，在最后的l=2，正好跳出while回圈，回傳的l值恰好是所插入的位置，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539163.html
標籤：其他
下一篇：機器學習：監督學習