go to  ForumEasy.com   
JavaPro
Home » Archive » Message


[Email To Friend][View in Live Context][prev topic « prev post | next post » next topic]
  Typical Algorithms
 
Subject: Typical Algorithms
Author: Alex_Raj
Posted on: 12/24/2013 01:27:47 AM

Search Algorithm

Linear Search -- O(n)

public class LinearSearch {
    /**
     * @param a Array of unsorted integers
     * @param val The value to search for
     * @return Array's index if found; -1 if not found. 
     */
    private static int search(int[] a, int val)
    {
        for(int k=0; k<a.length; k++){
            if(val==a[k])
                return k;
        }
        return -1;  // not found
    }
}


Binary Search -- O(logn)
public class BinarySearch {
    /**
     * @param a Array of sorted integers
     * @param val The value to search for
     * @param lo Low index of array
     * @param hi High index of array
     * @return Array's index if found; -1 if not found. 
     */
    public static int search(int[] a, int val, int lo, int hi)
    {
        while(lo<=hi){
            int mid = (lo + hi) >>> 1;
            int midVal = a[mid];
            if(val == midVal){
                return mid;
            }else if(val < midVal){
                hi = mid-1;
            }else{
                lo = mid+1;
            }
        }
        return -1;  // not found
    }

    /**
     * @param a Array of sorted integers
     * @param val The value to search for
     * @param lo Low index of array
     * @param hi High index of array
     * @return Array's index if found; -1 if not found. 
     */
    public static int searchWithRecursive(int[] a, int val, int lo, int hi)
    {
        int mid = (lo + hi) >>> 1;
        int midVal = a[mid];
        if(val == midVal)
            return mid;
        
        if(val < midVal)
            return searchWithRecursive(a, val, lo, mid-1);
        else
            return searchWithRecursive(a, val, mid+1, hi);
    }


Replies:


References:

 


 
Powered by ForumEasy © 2002-2022, All Rights Reserved. | Privacy Policy | Terms of Use
 
Get your own forum today. It's easy and free.