0 Replies - 1325 Views - Last Post: 23 November 2009 - 04:27 PM

#1 erik.price   User is offline

  • D.I.C Lover
  • member icon

Reputation: 486
  • View blog
  • Posts: 2,690
  • Joined: 18-December 08

Searching an Array Using Binary Search

Posted 23 November 2009 - 04:27 PM

Description: I've included bSearch (which takes 4 arguments) and binSearch (which takes 2 arguments). binSearch is intended for use when you feel lazy and want to search the whole array without typing a lot. bSearch is called by binSearch, or could be called by you to search a specific section of the arrayUses a recursive binary search to find an element in an array
def bSearch(arr, elem, low, high)
  mid = low+((high-low)/2).to_i
  if low > high 
    return nil
  end
  if elem < arr[mid]
    return bSearch(arr, elem, low, mid-1)
  elsif elem > arr[mid]
    return bSearch(arr, elem, mid+1, high)
  else
    return mid
  end
end

def binSearch(a, x)#automatically searches entire array
  return bSearch(a, x, 0, a.length)
end

#Example usage:
array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
puts binSearch(array, 9) #=> 8


Is This A Good Question/Topic? 0
  • +

Page 1 of 1