704. 二分查找

給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target ，寫一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1。

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

鏈接: 二分查找

這個(gè)題是一個(gè)最基礎(chǔ)的二分查找題目，需要你寫出二分查找最基礎(chǔ)的模板出來(lái)。
二分查找有許多的邊界問(wèn)題，每一次邊界的處理都要堅(jiān)持根據(jù)區(qū)間的定義來(lái)操作
，這就是循環(huán)不變量規(guī)則。

由題可知，該數(shù)組是一個(gè)升序的有序整型數(shù)組，

定義一個(gè)l變量，一個(gè)r變量，一個(gè)mid，分別表示的左值，右值，中值。
然后對(duì)每一次的mid中值進(jìn)行一次check，當(dāng)循環(huán)正常結(jié)束就是沒(méi)有target值，
返回-1.

代碼：

int search(int* nums, int numsSize, int target){int left=0,right=numsSize-1;int mid=(left+right)/2;while(left<right){if(nums[mid]>=target){right=mid;}else left=mid+1;mid=(left+right)/2;}if(nums[left]==target)return left;return -1;}

35. 搜索插入位置

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

請(qǐng)必須使用時(shí)間復(fù)雜度為 O(log n) 的算法。

輸入: nums = [1,3,5,6], target = 5
輸出: 2

輸入: nums = [1,3,5,6], target = 2
輸出: 1

輸入: nums = [1,3,5,6], target = 7
輸出: 4

鏈接: 搜索插入位置

這道題是二分查找的稍微進(jìn)階，相較于上一題需要考慮邊界情況，
以及最后的返回值。

將上一題的代碼拷貝下來(lái)

while(left<=right)
{if(nums[mid]==target){return mid;}if(nums[mid]>target){right=mid-1;}if(nums[mid]<target){left=mid+1;}mid=(left+right)/2;

這是部分代碼，從題中可知，
如果在遍歷的時(shí)候找到與target對(duì)應(yīng)的值，那么可以直接返回此時(shí)的下標(biāo)mid
如果沒(méi)有找到的話，循環(huán)結(jié)束后l，r，mid，這三個(gè)下標(biāo)哪個(gè)是正確的返回值呢。

由題意得，返回的是按照值大小順序插入的位置，所以返回了l的下標(biāo)。

代碼：

int searchInsert(int* nums, int numsSize, int target){int right =numsSize-1;int left=0;int mid=(right+left)/2;while(left<=right){if(nums[mid]==target){return mid;}if(nums[mid]>target){right=mid-1;}if(nums[mid]<target){left=mid+1;}mid=(left+right)/2;}return left;}

34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(log n) 的算法解決此問(wèn)題。

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例 2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

鏈接: 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

解題思路：
1.題目要求找出等于target大小的數(shù)組元素下標(biāo)的開(kāi)始位置和結(jié)束位置。
2.也就說(shuō)需要進(jìn)行兩次二分查找，一次找出開(kāi)始位置，一次找出結(jié)束位置
3.找出開(kāi)始位置：

1. 當(dāng)數(shù)組中有target元素的時(shí)候，我們可以將其分為兩個(gè)部分
2. 第一個(gè)部分范圍為所有 小于target的值
3. 第二部分則為所有 大于等于target的值
4. 由此可知，第二部分的開(kāi)頭位置的下標(biāo)即為所求

代碼：

        int l = 0;int r = nums.size() - 1;int mid = (l + r) / 2;while (l < r){if (nums[mid] >= target){r = mid;}else{l = mid + 1;}mid = (l + r) / 2;}

4.找出結(jié)束位置下標(biāo)：（同上）

1. 當(dāng)數(shù)組中有target元素的時(shí)候，我們可以將其分為兩個(gè)部分
2. 第一個(gè)部分范圍為所有 小于等于target的值
3. 第二部分則為所有 大于target的值
4. 由此可知，第一部分的結(jié)束位置的下標(biāo)即為所求

注意： 此時(shí)隨著循環(huán)更新的是l的值，所以更新方式應(yīng)改變。mid=（l+r+1）/2
代碼：

l = 0;
r = nums.size() - 1;
mid = (l + r+ 1) / 2;
while (l < r)
{if (nums[mid] <= target){l = mid;}else{r = mid - 1;}mid = (r + l+ 1) / 2;
}

每次求出也要檢查所求下標(biāo)對(duì)應(yīng)的值是否為target。

代碼：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> ans;//特殊情況處理if(nums.size()==0){ans.push_back(-1);ans.push_back(-1);return ans;}//初始位置int l = 0;int r = nums.size() - 1;int mid = (l + r) / 2;while (l < r){if (nums[mid] >= target){r = mid;}else{l = mid + 1;}mid = (l + r) / 2;}if (nums[l] == target) ans.push_back(l);else ans.push_back(-1);//結(jié)束位置l = 0;r = nums.size() - 1;mid = (l + r+ 1) / 2;while (l < r){if (nums[mid] <= target){l = mid;}else{r = mid - 1;}mid = (r + l+ 1) / 2;}if (nums[r] == target) ans.push_back(r);else ans.push_back(-1);return ans;}
};

結(jié)語(yǔ)

本期的二分查找到此結(jié)束，希望對(duì)各位有所幫助

我是Tom-貓
如果覺(jué)得有幫助的話，記得
一鍵三連哦ヾ(≧▽≦*)o。