Binary Search of an Integer array

The code below searches for a target integer and returns the index of the array if it is found else it returns a -1.

public class BinarySearch {
    public int search(int[] nums, int target) {
        int mid = 0;
	int start = 0;
	int end = nums.length-1;
        mid = (end - start)/2;
        boolean done = false;
            
        System.out.println("starting mid=" + mid);
        while(!done) {
            if (target == nums[mid]) {
                done = true;
                System.out.println("Found at " + mid);
                
            } else if (nums[mid] < target) {
		    start = mid;
            } else if (nums[mid] > target) {
		    end = mid;
            } 
	    System.out.println("new start= " + start+ ", end=" + end);
	    if (!done) {
		 if (end - start < 1) {
			 done = true;
			 mid = -1;
		 } else {
		      if (end - start > 1) {
			       mid = start + (end - start)/2;
		      } else if (nums[start] == target)
			      mid = start;
		      else if (nums[end] == target)
			      mid = end;
		      else {
			      mid = -1;
			      done = true;
		      }
		       System.out.println("mid=" + mid +", start=" + start + ",end=" + end);
		 }
	    }
            
        }
        return mid;
    }

  public static void main(String[] args) {
    int []arr = {-1,0,3,5,9,12,56,78,100,201};
    if (args.length < 1) {
        System.out.println("No arguments passed");
        return;
    }   
    int target = Integer.parseInt(args[0]);
    System.out.println("Looking for " + args[0]); 
    BinarySearch sol = new BinarySearch();
    sol.search(arr, target);
  }
}

The sample output is given below:

amit@amit-viao:/var/projects/java$ java BinarySearch 202
 Looking for 202
 starting mid=4
 new start= 4, end=9
 mid=6, start=4,end=9
 new start= 6, end=9
 mid=7, start=6,end=9
 new start= 7, end=9
 mid=8, start=7,end=9
 new start= 8, end=9
 mid=-1, start=8,end=9
 amit@amit-viao:/var/projects/java$ java BinarySearch 5
 Looking for 5
 starting mid=4
 new start= 0, end=4
 mid=2, start=0,end=4
 new start= 2, end=4
 mid=3, start=2,end=4
 Found at 3
 new start= 2, end=4
 amit@amit-viao:/var/projects/java$ 

The second sample given below returns the array index where it finds the target. If it does not find the target then it returns the index where it should have been in the array.

public class BinarySearch2 {
    public int search(int[] nums, int target) {
        int mid = 0;
	int start = 0;
	int end = nums.length-1;
        mid = (end - start)/2;
        boolean done = false;
	int lastVal = mid;
            
        System.out.println("starting mid=" + mid);
        while(!done) {
            if (target == nums[mid]) {
                done = true;
		lastVal = mid;
                System.out.println("Found at " + mid);
                
            } else if (nums[mid] < target) {
		    lastVal = mid+1;
		    start = mid;
            } else if (nums[mid] > target) {
		    lastVal = mid;
		    end = mid;
            } 
	    System.out.println("new start= " + start+ ", end=" + end);
	    if (!done) {
		 if (end - start < 1) {
			 done = true;
			 if (nums[end] > target)
				 lastVal = 0;
			 else if (nums[end] < target)
				 lastVal = 1;
			 mid = -1;
		 } else {
		      if (end - start > 1) {
			       mid = start + (end - start)/2;
		      } else if (nums[start] == target)
			      mid = start;
		      else if (nums[end] == target)
			      mid = end;
		      else {
			     if (end - start > 1) {
			       mid = start + (end - start)/2;
			      } else if (nums[start] == target)
				      mid = start;
			      else if (nums[end] == target)
				      mid = end;
			      else {
				      mid = -1;
				      done = true;
			      }

			      if (mid == -1) {
			        if (nums[end] < target)
					lastVal = end+1;
				else if (nums[end] > target)
					lastVal = end;

				if (nums[start] > target)
					lastVal = 0;
				else if (nums[start] > target)
					lastVal = start;
			      }

		      }
		       System.out.println("mid=" + mid +", start=" + start + ",end=" + end);
		 }
	    }
            
        }
        return lastVal;
    }

  public static void main(String[] args) {
    int []arr = {-1, 5,6,7,90,190};
    if (args.length < 1) {
        System.out.println("No arguments passed");
        return;
    }   
    int target = Integer.parseInt(args[0]);
    System.out.println("Looking for " + args[0]); 
    BinarySearch2 sol = new BinarySearch2();
    System.out.println("Target position=" + sol.search(arr, target));
  }
}

The output is given below

amit@amit-viao:/var/projects/java$ java BinarySearch2 2
 Looking for 2
 starting mid=0
 new start= 0, end=0
 Target position=1
 amit@amit-viao:/var/projects/java$ javac BinarySearch2.java
 amit@amit-viao:/var/projects/java$ java BinarySearch2 2
 Looking for 2
 starting mid=2
 new start= 0, end=2
 mid=1, start=0,end=2
 new start= 0, end=1
 mid=-1, start=0,end=1
 Target position=1
 amit@amit-viao:/var/projects/java$ java BinarySearch2 22
 Looking for 22
 starting mid=2
 new start= 2, end=5
 mid=3, start=2,end=5
 new start= 3, end=5
 mid=4, start=3,end=5

Be the first to comment

Leave a Reply

Your email address will not be published.


*