Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Binary Search in DSA(Data Structure and Algorithms)

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 100
    Comment on it

    Binary search is simple and fast search algorithm which works on the principle of divide and conquer.

    It will work properly when the data collected is in sorted form.

    It is having run-time complexity of (log n).

    This searching algorithm search a item by comparing the middle item of the given list.

    If matches occurs then index of item is returned.

    If middle item is greater than item then item is searched in sub-array to the right of the middle item other wise item is search in sub-array to the left of the middle item.

    This process will be continued on sub-array as well until the size of subarray reduces to zero.

    Use the given two formulas

    i.)To determine the half of the array

    mid = low + (high - low) / 2
    

    ii.) To find the new mid value again.

    low = mid + 1
    mid = low + (high - low) / 2
    

    Pseudocode:-

    Procedure binary_search
       A  sorted array
       n  size of array
       x  value ot be searched
    
       Set lowerBound = 1
       Set upperBound = n 
    
       while x not found
    
          if upperBound < lowerBound 
             EXIT: x does not exists.
    
          set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
    
          if A[midPoint] < x
             set lowerBound = midPoint + 1
    
          if A[midPoint] > x
             set upperBound = midPoint - 1 
    
          if A[midPoint] = x 
             EXIT: x found at location midPoint
    
       end while
    
    end procedure
    

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: