```//Binary Search implementation //Time Complexity: O (log n) //return int {-1 , mid index}
int binarySearch(int tar, vector<int>& arr){
int lo=0, md, hi=arr.size()-1;
while(hi>=lo){
md = lo + (hi - lo) / 2;
if(arr[md]==tar) return md;
else if(arr[md]<tar) lo=md+1;
else hi=md-1;
}
return -1;
}
---------------------------------------------------------------------------------------------------
//Binary Search by using Stls //Time Complexity: O (log n)
// for binary search in containers like vector (let target element=6)
binary_search(v.begin(), v.end(), 6);
// return 1 or 0 as present or not
---------------------------------------------------------------------------------------------------
//binary search with lower and upper bound by using stls
int x, ans; //x is passing value, ans is a value you want, v --> vector or any container
ans = lower_bound(v.begin(), v.end(), x) - v.begin(); //ans >= x (equal number or first number after x)
ans = upper_bound(v.begin(), v.end(), x) - v.begin(); // ans > x (first number after x)

//implementation
int lower_bound(vector<int> nums, int target){
int l = 0, r = nums.size()-1, m = 0;
while(l < r) {
m = (l+r)/2;
if(nums[m] < target)
l = m+1;
else
r = m;
}
return r;
}

int upper_bound(vector<int> nums, int target){
int l = 0, r = nums.size()-1, m = 0;
while(l < r) {
m = (l+r)/2;
if(nums[m] <= target)
l = m+1;
else
r = m;
}
return r;
}
---------------------------------------------------------------------------------------------------
// Two Pointer implementation
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
int isPairSum(int A[], int N, int X)
{
// represents first pointer
int i = 0;

// represents second pointer
int j = N - 1;

while (i < j) {

int curSum = A[i]+arr[j];

// If we find a pair
if curSum == X)
return 1;

// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (curSum < X)
i++;

// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return 0;
}```
```int search(int* arr, int n, int key) {
int si = 0;
int ei = n-1;
//     core concept : if array is rotated and we visited any index then one part
// of array is going to be sorted
while(si <= ei){
int mid = (si + ei)/2;

if(arr[mid] == key){
return mid;
}
if(arr[mid]  >= arr[si]){
//             if mid == si this means left part has one element and that is sorted
//           left  array is sorted
if(key < arr[mid] && key >= arr[si]){
ei = mid - 1;
continue;
}else{
si = mid + 1;
}
}
if(arr[mid]  <= arr[ei]){
//             here arr[mid] can be equal to arr[ei] if there is only one
//             element in whole array
//             righty array is sorted
//
if(key <= arr[ei]  && key > arr[mid]){
si = mid + 1;

}else{
ei = mid - 1;
}

}
}
return -1;
}```
star

Wed Aug 17 2022 20:36:19 GMT+0000 (Coordinated Universal Time) https://www.geeksforgeeks.org/implementing-upper_bound-and-lower_bound-in-c/

#c++ #math #binary_search #two_pointer
star

Sun Jul 31 2022 18:53:43 GMT+0000 (Coordinated Universal Time) https://www.codingninjas.com/codestudio/guided-paths/data-structures-algorithms

#rotated_array #binary_search