題目：

704. 二分查找

難度簡單1197收藏分享切換為英文接收動(dòng)態(tài)反饋

給定一個(gè)?n?個(gè)元素有序的（升序）整型數(shù)組?nums?和一個(gè)目標(biāo)值?target??，寫一個(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

?

提示：

1. 你可以假設(shè)?nums?中的所有元素是不重復(fù)的。

2. n?將在?[1, 10000]之間。

3. 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í)沒有意識(shí)到讓right和left等于mid+1/-1就已經(jīng)慢慢趨近這個(gè)結(jié)果了

第一種對法：

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;

????}

};

正常的二分