Binary search

Binary search or half-interval search is a fast search algorithm to find the position of a target value in a sorted array. The run-time complexity of this algorithm is Ο(log n).

Binary search
Binary search

In binary search, the target value is compared to the middle element of the array; if they are not equal, the half of array which target can not lie, is eliminated and the search continues in the remaining half until it is successful.

1. Algorithm

  1. Set L to 0 and R to n − 1.
  2. If L > R, the search terminates as unsuccessful.
  3. Set m (the position of the middle element) to the floor of (L + R) / 2.
  4. If A[m] < T(target value), set L to (m + 1) and go to step 2. If A[m] > T, set R to (m – 1) and go to step 2.
  5. Now Am = T, the search is done; return m.

2. Java code

/**
 * Array should be sorted asc
 * The implementation is not recursive
 * Complexity of the algorithm
 * Best: O(1)
 * Worst: O(logn)
 */
 public static int binarySearch(int[] array, int val){
     int low = 0;
     int high = array.length - 1;
     while(low < high){
         int mid = (high + low) / 2;
         if(array[mid] == val)
             return mid;
         else if(array[mid] < val)
             low = mid +1;
         else
             high = mid - 1;
     }
     return -1;
 }

2.1. Recursive implementation

/**
 * Array should be sorted asc
 * The implementation is recursive
 * Complexity of the algorithm
 * Best: O(1)
 * Worst: O(log n)
 */
 public static int binarySearch(int[] array, int val, int low, int high){
     int mid = (high + low) / 2;
     if(high < low)
         return -1;
     if(array[mid] == val)
         return mid;
     else if(array[mid] < val)
         return binarySearch(array, val,mid + 1, high);
     else
         return binarySearch(array,val,low ,mid - 1);
 }
Advertisements

Linear search

Linear search or sequential search is a simple search algorithm for finding a target within a list. In this type of search, a sequential search checks every element within the list for a target value till a match is found. Otherwise, the search continues until the end of the list.

In the best case, the complexity of this algorithm is O(1) in the worst case, is O(n).

1. Algorithm

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Return Element x Found at index i and go to step 8
Step 7: Return -1
Step 8: Exit

2. Java Code

/**
* Simple Linear Search
* Complexity of the algorithm
* Best: O(1)
* Worst: O(n)
*/
public static int linearSearch(int[] array, int val){

    for (int i = 0; i < array.length; i++) {
        int num = array[i];
        if(val == num){
            return i;
        }
     }
     return -1;
}