Algorithms-Reference

Binary Search

Classic Application of Binary Search

Binary Search finds the position of a target value in a sorted array. The complexity for this algorithm is

- Worst-case performance        O(log n)
- Best-case performance         O(1)
- Average performance           O(log n)
- Worst-case space complexity   O(1)

class BinarySearch(object):
    def search(self, nums, target):
        low = 0 
        high = len(nums)-1
        while low<=high:
            mid = (low+high)//2
            if nums[mid]==target:
                return mid
            if nums[mid]>target:
                high=mid-1
            else:
                low=mid+1
        
        return -1

print(BinarySearch().search([-1,2,4,6,12,22,34,54,67,76,98,645,896,2342],645))

11

print(BinarySearch().search([-1,2,4,6,12,22,34,54,67,76,98,645,896,2342],949))

-1

Get a Separator in a rotated sorted Array

Modification of Binary search

class SortedSeparator(object):
    def getSeparator(self,nums):
        lo=0
        hi=int(len(nums)-1)
        while lo<hi:
            mid=int((lo+hi)/2)
            if nums[mid]>nums[hi]:
                lo=mid+1
            else:
                hi=mid   
        return lo
print(SortedSeparator().getSeparator([7,8,9,10,12,23,45,67,1,3,4,5,6]))

8