Understanding binary #search
▻https://hackernoon.com/understanding-binary-search-e82d7bcbc06f?source=rss----3a8144eabfe3---4
Suppose, numbers is a list/array of integers that are sorted in nondecreasing order. We need to determine whether an element x is present in the list or not. There are n elements in the list .Linear searchBefore using binary search let’s check how linear search will perform in this problem.Let’s, n = 10⁶ ( here,numbers is a list of 10⁶ integers).If x is present at the first position of the list then we will get our expected result at the first iteration. This will work in O(1) time. Pretty fast! NO?But if x is present at 10⁶th position(or not present in the list) then it will take O(n) time to calculate the result and if we search for n times then time complexity will be O(n²), pretty slow, NO?So we can say that, at worst case linear search will work in O(n²) time complexity (for n number of (...)