力扣：二分查找
題目：
704. 二分查找
難度簡(jiǎn)單1197收藏分享切換為英文接收動(dòng)態(tài)反饋
給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target? ，寫(xiě)一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9輸出: 4解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2輸出: -1解釋: 2 不存在 nums 中因此返回 -1
?
提示：
你可以假設(shè) nums 中的所有元素是不重復(fù)的。
n 將在 [1, 10000]之間。
nums 的每個(gè)元素都將在 [-9999, 9999]之間。
第一種錯(cuò)法：
class Solution {
public:
? ? int search(vector<int>& nums, int target) {
? ? ? ? ? ? int right=nums.size()-1,left=0;
? ? ? ? ? ? while(right>=left){
? ? ? ? ? ? ? ? int mid = (right+left)/2;
? ? ? ? ? ? ? ? if(nums[mid]>target){
? ? ? ? ? ? ? ? ? ? right=mid-1;
? ? ? ? ? ? ? ? }else if(nums[mid]<target){
? ? ? ? ? ? ? ? ? ? left=mid+1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(nums[mid]==target){
? ? ? ? ? ? ? ? ? ? return mid;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? right--,left++;//這里錯(cuò)了
? ? ? ? ? ? }
? ? ? ? ? ? return -1;
? ? }
};
想著要讓right<left但是當(dāng)時(shí)沒(méi)有意識(shí)到讓right和left等于mid+1/-1就已經(jīng)慢慢趨近這個(gè)結(jié)果了
第一種對(duì)法：
class Solution {
public:
? ? int search(vector<int>& nums, int target) {
? ? ? ? ? ? int right=nums.size()-1,left=0;
? ? ? ? ? ? while(right>=left){
? ? ? ? ? ? ? ? int mid = (right+left)/2;
? ? ? ? ? ? ? ? if(nums[mid]>target){
? ? ? ? ? ? ? ? ? ? right=mid-1;
? ? ? ? ? ? ? ? }else if(nums[mid]<target){
? ? ? ? ? ? ? ? ? ? left=mid+1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(nums[mid]==target){
? ? ? ? ? ? ? ? ? ? return mid;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return -1;
? ? }
};
兩邊為閉區(qū)間的寫(xiě)法：[1 2 3 4 5](像這樣)
第二種對(duì)法：
class?Solution?{
public:
????int?search(vector<int>&?nums,?int?target)?{
????????????int?right=nums.size(),left=0;
????????????while(right>left){
????????????????int?mid?=?left+((right-left)>>1);
????????????????if(nums[mid]>target){
????????????????????right=mid;
????????????????}else?if(nums[mid]<target){
????????????????????left=mid+1;
????????????????}else{
????????????????????return?mid;
????????????????}
????????????}
????????????return?-1;
????}
};
左閉右開(kāi)[1 2 3 4 5 6)的寫(xiě)法
