Problem Statement:
You are given an sorted ascending array, you need to find the fixed point.
A fixed point is an element in the array, such that index i and arr[i] are same.
Example
Input: {-7, -4, 0, 3, 6} Output: 3 Because arr[3] == 3
Solution
There are multiple ways to solve this problem:
1. Linear Search
2. Binary search
1. Linear Search:
Here we check for every element of arr[i] with i and then return that element
Time Complexity: O(n)
2. Binary Search:
As the array is sorted, we can use binary search.
In binary search, we check if the middle element is a fixed point or not.
else, if the index of the middle element is greater than value at the index, then move towards right.
else, move towards left.
Time Complexity: O(logn)
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <sstream> using namespace std; int linear_earch(int arr[], int n) { int i; for(i = 0; i < n; i++) { if(arr[i] == i) return i; } return -1; } int binary_search(int arr[], int low, int high) { if(high >= low) { int mid = (low + high)/2; if(mid == arr[mid]) return mid; if(mid > arr[mid]) return binary_search(arr, (mid + 1), high); else return binary_search(arr, low, (mid -1)); } return -1; } /* Driver code */ int main() { int arr[] = {-1, 0, 1, 3, 5, 10}; int n = sizeof(arr)/sizeof(arr[0]); cout << "Fixed Point is using linear search " << linear_earch(arr, n)<<endl; cout << "Fixed Point is using binary search " << binary_search(arr, 0, n-1)<<endl; return 0; }
Output:
Fixed Point is using linear search 3 Fixed Point is using binary search 3