2 votes 2 votes .Given an array of distinct integers A[1, 2,…n]. Find the tightest upper bound to check the existence of any index i for which A[i]=i. Ans should be O(log n) right by doing binary search ?? Algorithms algorithms array searching vani-booklet + – Hirak asked May 21, 2019 retagged Jul 8, 2022 by Lakshman Bhaiya Hirak 1.2k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Show 15 previous comments srestha commented May 21, 2019 reply Follow Share put Merge Sort for sorting all elements. Then found element in log n time 0 votes 0 votes Satbir commented May 21, 2019 reply Follow Share but O(n) is better than O(n log n) so we should go with O(n) right ? 0 votes 0 votes srestha commented May 21, 2019 reply Follow Share yes, chking every element can do it 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes IF it is giving that array is sorted.. Then O(log n) will be correct answer. vikash_thakur answered May 25, 2019 vikash_thakur comment Share Follow See all 0 reply Please log in or register to add a comment.