704.二分查找：
給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target 伪朽，寫一個(gè)函數(shù)搜索 nums 中的 target沼填，如果目標(biāo)值存在返回下標(biāo)冕房，否則返回 -1怒竿。
鏈接：https://leetcode.cn/problems/binary-search
示例 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]之間赵刑。
初步思考：
關(guān)鍵詞：有序分衫、不重復(fù)。進(jìn)而選擇使用二分查找的方法般此，對(duì)數(shù)組進(jìn)行遍歷蚪战。
- 過程：
設(shè)定左右指針
找出中間位置牵现，并判斷該位置值是否等于 target
nums[mid] == target 則返回該位置下標(biāo)
nums[mid] > target 則右側(cè)指針移到中間
nums[mid] < target 則左側(cè)指針移到中間
時(shí)間復(fù)雜度：O(logN)
第一種方法，也就是定義 target 是在一個(gè)在左閉右閉的區(qū)間里[left, right] （這個(gè)很重要非常重要）邀桑。
區(qū)間的定義這就決定了二分法的代碼應(yīng)該如何寫瞎疼，因?yàn)槎xtarget在[left, right]區(qū)間，所以有如下兩點(diǎn)：
- while (left <= right) 要使用 <= 壁畸，因?yàn)閘eft == right是有意義的贼急，所以使用 <=
- if (nums[middle] > target) right 要賦值為 middle - 1，因?yàn)楫?dāng)前這個(gè)nums[middle]一定不是target捏萍，那么接下來要查找的左區(qū)間結(jié)束下標(biāo)位置就是 middle - 1
代碼如下：
#include<iostream>
using namespace std;
class Solution {
public:
int search(int nums[], int target,int length) {
int left = 0, right = sizeof(nums) - 1;
while (left <= right) {
//int mid = (left+right)/2; 可能溢出
int mid = left+(right - left) / 2 ;
int num = nums[mid];
if (num == target) {
return mid;
}
else if (num > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
};
int main()
{
Solution C;
int nums[] = { 2, 5, 7, 9, 11 };
int target;
target = 7;
int out=C.search(nums,target,sizeof(nums)/sizeof(nums[0]));
cout<<out;
}
進(jìn)一步思考：
如果說定義 target 是在一個(gè)在左閉右開的區(qū)間里竿裂，也就是[left, right) ，那么二分法的邊界處理方式則截然不同照弥。
有如下兩點(diǎn)：
- while (left < right)腻异，這里使用 < ,因?yàn)閘eft == right在區(qū)間[left, right)是沒有意義的
- if (nums[middle] > target) right 更新為 middle，因?yàn)楫?dāng)前nums[middle]不等于target这揣，去左區(qū)間繼續(xù)尋找悔常，而尋找區(qū)間是左閉右開區(qū)間，所以right更新為middle给赞，即：下一個(gè)查詢區(qū)間不會(huì)去比較nums[middle]
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定義target在左閉右開的區(qū)間里机打，即：[left, right)
while (left < right) { // 因?yàn)閘eft == right的時(shí)候，在[left, right)是無效的空間片迅，所以使用 <
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle; // target 在左區(qū)間残邀，在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1; // target 在右區(qū)間，在[middle + 1, right)中
} else { // nums[middle] == target
return middle; // 數(shù)組中找到目標(biāo)值柑蛇，直接返回下標(biāo)
}
}
// 未找到目標(biāo)值
return -1;
}
};
總結(jié)：
二分法對(duì)于開閉區(qū)間的理解十分重要芥挣，對(duì)于區(qū)間的邊界處理不當(dāng)會(huì)導(dǎo)致結(jié)果的錯(cuò)誤。
參考：手把手帶你撕出正確的二分法 | 二分查找法 | 二分搜索法_嗶哩嗶哩_bilibili
拓展延伸：
Binary Search兩大基本原則：
- 每次都要縮減搜索區(qū)域耻台。
- 每次縮減不能排除潛在答案空免。
(這部分代碼仍存在死循環(huán)的bug)
First Occurance：
尋找元素第一次出現(xiàn)時(shí)的位置：
循環(huán)條件：l<r；縮減搜索空間:l=mid+1,r=mid
//尋找某數(shù)第一次出現(xiàn)
int FirstOccurance(int nums[], int target, int length)
{
int l = 0, r = length - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] < target)
{
l = mid+1;
}
else {
r = mid;
}
}
return l;
}
Last Occurance：
尋找元素最后一次出現(xiàn)時(shí)的位置：
循環(huán)條件：l<r盆耽；縮減搜索空間:l=mid,r=mid-1
//尋找某數(shù)最后一次出現(xiàn)
int LastOccurance(int nums[], int target, int length)
{
int l = 0, r = length - 1;
while (l < r)
{
int mid = l + (r - l+1) / 2;//向上取整防止死循環(huán)
if (nums[mid] > target)
{
r = mid - 1;
}
else {
l = mid;
}
}
return l;
}
Closest：
尋找與元素大小最接近的數(shù)的位置：
循環(huán)條件：l<r-1蹋砚；縮減搜索空間:l=mid,r=mid
//尋找最接近的值
int Closest(int nums[], int target, int length)
{
int l = 0, r = length - 1;
while (l < r-1)
{
int mid = l + (r - l) / 2;
if (nums[mid] < target)
{
l = mid;
}
else {
r = mid;
}
}
if (nums[r] < target)
{
return r;
}
else if(nums[r]>target)
{
return 1;
}
else
{
return target - nums[l] < nums[r] - target ? l : r;
}
}
參考鏈接：https://www.bilibili.com/video/BV1Ng4y1q7E3?spm_id_from=333.999.0.0
更優(yōu)化算法：
在b站中看到一個(gè)視頻，對(duì)二分查找再一次進(jìn)行了較為詳細(xì)的講解摄杂，其思路與以上的又大為不同坝咐，可以說是這類題目的一個(gè)通法，看完后析恢，給我了大大的啟發(fā)墨坚，有了融會(huì)貫通的感覺。該視頻給出了關(guān)于二分查找這類問題的一個(gè)通用模板氮昧。
視頻鏈接：二分查找為什么總是寫錯(cuò)框杜？_嗶哩嗶哩_bilibili
這里將l的值設(shè)置為-1浦楣，r的值設(shè)置為N，這與之前的方法都是大為不同的咪辱。這種類型其實(shí)就是左開右開的類型振劳，可以讓中間值m一直處于[0,N]以內(nèi)。同時(shí)油狂，在更新指針時(shí)历恐，避免了多次討論l=m+1,r=m-1等情況，統(tǒng)一為l=m,r=m专筷，可以作為一種通用的方法弱贼。這樣我們的問題就轉(zhuǎn)換為了以下步驟：
- 確定IsBlue()判斷條件
- 考慮返回l還是r
- 套用模板
- 針對(duì)具體進(jìn)行一系列的后處理
視頻中還給出了四個(gè)具體的例子：
這邊自己嘗試將以上的偽代碼進(jìn)行了實(shí)現(xiàn)：
//找到第一個(gè)>=target的元素
int target1(int nums[], int target,int length)
{
int l = -1;
int r = length;
while ((l + 1) != r)
{
int m = (l + r) / 2;
//cout << "m=" << m<<endl;
if (nums[m]<target)
{
l = m;
}
else
{
r = m;
}
}
return r;
}
//找到最后一個(gè)<target的元素
int target2(int nums[], int target, int length)
{
int l = -1;
int r = length;
while ((l + 1) != r)
{
int m = (l + r) / 2;
//cout << "m=" << m<<endl;
if (nums[m] < target)
{
l = m;
}
else
{
r = m;
}
}
return l;
}
//找到第一個(gè)>target的元素
int target3(int nums[], int target, int length)
{
int l = -1;
int r = length;
while ((l + 1) != r)
{
int m = (l + r) / 2;
//cout << "m=" << m<<endl;
if (nums[m] <= target)
{
l = m;
}
else
{
r = m;
}
}
return r;
}
//找到最后一個(gè)<=target的元素
int target4(int nums[], int target, int length)
{
int l = -1;
int r = length;
while ((l + 1) != r)
{
int m = (l + r) / 2;
//cout << "m=" << m<<endl;
if (nums[m] <= target)
{
l = m;
}
else
{
r = m;
}
}
return l;
}
本文參考了網(wǎng)上多位大佬的視頻教程以及文字教程，屬于是對(duì)這類二分查找問題的一次較為深入的學(xué)習(xí)磷蛹，在學(xué)習(xí)過程中記錄下來了以上筆記吮旅，總結(jié)了各種不同的算法思路以及方法。
補(bǔ)充：
數(shù)組在作為參數(shù)傳入函數(shù)時(shí)味咳，數(shù)組的大小并不會(huì)傳入庇勃，數(shù)組是由指針的形式傳入函數(shù)的。所以在函數(shù)中需要訪問原數(shù)組大小時(shí)候槽驶，需要將原數(shù)組的長(zhǎng)度一并傳入责嚷。
(6條消息) C語言的那些坑（數(shù)組做參數(shù)計(jì)算大小問題）_零一匠的博客-CSDN博客
CSDN同步更新，歡迎關(guān)注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode學(xué)習(xí)筆記,HTML+CSS+JS,數(shù)據(jù)結(jié)構(gòu)領(lǐng)域博主
