# Binary search
###### tags: `Study_aboard`
## Binary search algorithm
https://www.cnblogs.com/grandyang/p/6854825.html
Timing : To search a sorted array
Complexity : $log{_2}{N}$
Specify left, right, mid, compare mid with the target and change right or left continuously (夾擊法)
### 1. Find Exactly The Target
==Watch out and remeber left < right, left = mid+1, right = mid==
Explain: If left=right=mid, right will = mid = itself and will generate loop forever
```cpp
int find(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return -1;
}
```
### 2. Find the first number that is greater or equal to the target
```cpp
// !!! the only difference between 1 and 2 is that it do not return when nums[mid]==target
int find(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return right;
}
```
right-1 is also the larget element that is smaller than the target
### 3. Find the smallest elements that is greater than the target
```cpp
// the difference between 2 and 3 is that when it is equal, 2 will move right to mid, 3 will move left to mid
int find(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) left = mid + 1;
else right = mid;
}
return right;
}
```
## Search in Rotated Sorted Array
Initial: 找到變更點，比較與target間的大小後，對區間進行binary search
Problem: 找到變更點 time complexity = O(n)
Sol: 不找變更點，而是在binary search 中判斷區間為ascending or descending，下圖為0,1,2,3,4,5,6,7 所有rotate的可能
==找到規律，若mid<right，則mid~right為ascending orders, 若mid<right，則左半邊為ascending orders==
```cpp
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[right]) { // ascending
if (nums[mid] < target && nums[right] >= target) left = mid + 1; // if nums[mid]<target<nums[right]
else right = mid - 1; // if target<nums[mid] || target>nums[right]
// notice : when target>nums[right], means that the rotated part is in 0~mid, thus right=mid-1
} else { // means left to mid is ascending
if (nums[left] <= target && nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
}
return -1;
}
};
```
## Search in Rotated Sorted Array II
==Hard to me==
Initial:
Problem: duplicate may cause error when mid=right
ex: 1111112111, we do not know which side we should sort
Sol: when mid=right, right-=1, and run the loop again until they are not equal
```cpp
class Solution {
public:
bool search(vector<int>& nums, int target) {
int n = nums.size(), left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return true;
if (nums[mid] < nums[right]) {
if (nums[mid] < target && nums[right] >= target) left = mid + 1;
else right = mid - 1;
} else if (nums[mid] > nums[right]){
if (nums[left] <= target && nums[mid] > target) right = mid - 1;
else left = mid + 1;
} else --right;
}
return false;
}
};
```
## Find First and Last Position of Element in Sorted Array
Find the first greater or equal position - binary search type II
```cpp
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left=0, right=nums.size()-1, mid;
vector <int> res;
if(nums.size()==0){
res.push_back(-1);
res.push_back(-1);
return res;
}
while(left<right){
mid = left + (right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
if(nums[right]!=target){
res.push_back(-1);
res.push_back(-1);
return res;
}
res.push_back(right);
for(int i=right+1;i<nums.size();i++){
if(nums[i]==target) right++;
else break;
}
res.push_back(right);
return res;
}
};
```
## Longest Increasing Subsequence ==Important==
2. Method 2 : Combine with Binary search
DP + Greedy + Binary Search tree
[solution by geeksforgeeks](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/)
## Count of Smaller Numbers After Self
Initial: want to sort the array first and then binary search for the lowest bound of the target
Problem: TLE
Solution: No solution yet
```cpp
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> res,sorted_nums = nums;
sort(sorted_nums.begin(),sorted_nums.end());
for(int i=0;i<nums.size();i++){
int target = nums[i];
// binary search type II
int left=0, right=sorted_nums.size()-1;
while(left<right){
int mid = left+ (right-left)/2;
if(sorted_nums[mid]<target) left=mid+1;
else right=mid;
}
// There are 2 situations
// 1. no other is bigger than the target -> return right
// 2. there is some number bigger than the target -> return rigjt-1
if(sorted_nums[right]==target){
res.push_back(right);
sorted_nums.erase(sorted_nums.begin()+right);
}
else{
res.push_back(right-1);
sorted_nums.erase(sorted_nums.begin()+right-1); // erase the target
}
}
return res;
}
};
```
revised version:
==不用先sort整串數列==，而是由==最後一位數開始==(最後一位的右方為空，因此可以作為新數列的第一位)binary search的插入新數列。而其所在的位置即為小於的數字個數。
```cpp
// Binary Search
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
int left = 0, right = t.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (t[mid] >= nums[i]) right = mid;
else left = mid + 1;
}
res[i] = right;
t.insert(t.begin() + right, nums[i]);
}
return res;
}
};
```
Sign in with Wallet
Connect another wallet