There are problems which can be easily solved using linear time, can be optimized to log N time complexity using binary search concept. Today we will a problem which applies binary search concept to solve one such problem. Problem statement Given an array containing only 0s and 1s in sorted order. Find the first occurrence of 1 in array. Same problem can be asked as find last occurrence of 0. Other variant is to find number of ones of zeroes in given array. Analysis Linear time solution is easy. Just go through array and once you hit 1, return the index. Great!
Read full article from Algorithms and Me: Application of binary search
No comments:
Post a Comment