Binary search on sorted array (Java Code)

Problem - What is efficient way to search a sorted array .

Observations :

 For searching an element in the array strategy depends on nature of data in array .

1. If array is not sorted there is no other way than sequential scan of the array .
2. If array is sorted but length is not known then jump search ( jump with constant size or Fibonacci number or exponential factor ) could be used to improve sequential scan .
3. If array is sorted and length is known then binary search is best way to do the search .

Binary is search is well known divide and conquer algorithm .
It can be implemented using recursion or without recursion using stack .

Algorithm Complexity :  worst case  Ω(log2(n)) , average case O(log2(n)) , best case O(1) .


Sequential Search for sorted array 

To search  7th place we have to traverse to 7 places.  which proves complexity  O(n) .

Binary Search for sorted array 

To search 7th place ,  we have to traverse 3 places . which proves complexity O(log2(n)).


Java Code 

package com.salpe.arrays;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 @Test
 public void testSuccess() {

  int[] arr = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };

  int result1 = searchWithR(arr, 7, 0, arr.length - 1);

  Assert.assertEquals(result1, 7);

  int result2 = searchWithoutR(arr, 7, 0, arr.length - 1);

  Assert.assertEquals(result2, 7);

 }

 public int searchWithR(int[] arr, int value, int lo, int hi) {

  // exit condition
  if (lo > hi) {

   // return special value if term is not found;

   return -1;
  }

  int mid = (lo + hi) / 2;

  if (arr[mid] == value) {

   return mid;

  } else if (value < arr[mid]) {

   // change value of high , one position left of mid
   return searchWithR(arr, value, lo, mid - 1);

  } else {

   // change value of low , one position right of mid
   return searchWithR(arr, value, mid + 1, hi);
  }

 }

 public int searchWithoutR(int[] arr, int value, int lo, int hi) {

  // condition to check less than or equal* is very important
  while (lo <= hi) {

   int mid = (lo + hi) / 2;

   if (arr[mid] == value) {

    return mid;

   } else if (value < arr[mid]) {

    // change value of high , one position left of mid
    hi = mid - 1;

   } else {

    // change value of low , one position right of mid
    lo = mid + 1;
   }

  }

  // return is case no result found
  return -1;
 }

}