//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; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter