binary search

[looji]

hi im a beginer

can anybody help me to convert this code (c++) to ruby(works in flowstone) ??

Code: Select all


#include <conio.h>
#include <iostream.h>

main()
{
    int n;
    cout<<"array size???" ;
    cin>>n;
    cout << "_____________";
    cout<<endl;
    int a[n];
    for(int i=0;i<n;i++)
    {
       cin>> a[i];
    }
   
   
    cout<<endl;
     cout << "_____________";
        cout<<endl;
    for(int i=0;i<n;i++)        //sort
    {
        for(int j=0;j<n-1;j++)
        {
            if(a[j+1]>a[j])
            {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
   
    for(int i=0;i<n;i++)        //namayesh
    {
        cout<<a[i]<<" ";
    }
     cout<<endl;
      cout << "_____________";
     cout<<endl;
    int f;
    cin>>f;
    int start=0;                 //Binary search
    int end=n-1;
    while(start<=end)       
    {
        int mid=(start+end)/2;
        if(a[mid]==f)
        {
            cout<<"found at "<<mid;
            break;
        }
        if(a[mid]<f)
            end=mid-1;
        else if(a[mid]>f)
            start=mid+1;
    }
    if(start>end)
        cout<<"Not found!";
   
    getch();
   
}



[tulamide]

The question is if you gain any advantage from it. Binary search, a divide and conquer algorithm, is very stable and therefore the best choice for very large arrays. However, in pure Ruby the code gets interpreted, while the built-in search methods are compiled c-code.

binary search needs a sorted array to start with. You sort an array simply by using

Code: Select all

myarray.sort!

For the binary search, there's a premade code block on codecodex, using recursiveness:

Code: Select all

def binary_search(array, key, low=0, high=array.size-1) 
  return -1 if low > high 
  mid = (low + high) / 2 
  return mid if array[mid]==key 
  if array[mid] > key 
    high = mid - 1 
  else 
    low = mid + 1 
  end 
  binary_search(array, key, low, high)   
end 

If this doesn't help you, please provide a description of how you want to make use of it.