一.兩道LeetCode題

首先來兩道算法題舉例，來初步探討二分查找

278.First Bad Version

先貼上代碼

// Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public:int firstBadVersion(int n) {int lower = 1, upper = n, mid;while(lower < upper) {mid = lower + (upper - lower) / 2;if(!isBadVersion(mid)) lower = mid + 1; else upper = mid;}return lower; } };

題目表意為有一大堆數字，分別是0，0，0，0，······1，1，1，1，1，1····

隨后要求我們找到第一個1出現的位置，算法如上，關于low與high是否加一減一，我們隨后開始討論

35. Search Insert Position

題目：Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

要求我們找出插入位置并返回，我們可以利用二分查找直接解決這道題

貼上代碼

class Solution { public:int searchInsert(vector<int>& nums, int target) {int high = nums.size()-1;int low = 0;int mid;while(low<=high){mid = (low + high )/2;else if(nums[mid]>=target)high = mid -1;else if(nums[mid]<target)low = mid +1;}return low;} };

二.探討二分查找

1.中位數概念

中位數有兩種，分別為
下位中位數：(length-2)/2
上位中位數：length/2

通常中位數寫法：
(length-1)/2

算法中寫法：
mid = low+(lhigh-low)/2;
注意不要求快，否則溢出導致程序失敗

2.其他問題

這里探討的是為什么上限high有時候是賦值mid有時是賦值mid-1

在一般的數組查找中，通常使用mid-1
但在256問題中，使用的卻是mid
并且這些選項都是唯一性，

但是，細心的我們可以發現，兩者的while條件不同，
所以說，while條件匹配的不同
如果是<= 那high 必須取mid-1
如果是< 那high 必須取mid

為了統一標準，以后寫代碼寫同一種比較好。

三.兩種二分查找變形

1.找到第一個等于目標的值

void find(vector<int>&nums){int lo = 0,hi = nums.size()-1;int mid;while(lo<=hi){mid = lo + (hi-lo)/2;if(nums[mid]<target)lo = mid + 1;elsehi = mid - 1;}return lo; }

2.找到最后一個等于目標的值

void find(vector<int>&nums){int lo = 0,hi = nums.size()-1;int mid;while(lo<=hi){mid = lo + (hi-lo)/2;if(nums[mid]>target)hi = mid - 1;elselo = mid + 1;}return hi; }

轉載于:https://www.cnblogs.com/vhyz/p/7241577.html

總結

以上是生活随笔為你收集整理的算法与数据结构之二分查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。