Array: Binary Search

package Array;

/**
 * Created by aarushi on 1/5/21.
 */
public class ArraySearchBinary {
    /*Step 1: The array must be sorted
      Step 2: Assign the lowBound and upBound at the extreme ends of the array
      Step 3: Find the middle element
      Step 4: if the key is less than the middle element, search only in the first half of the array.
              upBound=mid-1
              if the key is greater than the middle element, search only in the second half of the array.
              lowBound=mid+1
              if the key is equal to the mid element, end the search
     */

    public static boolean binarySearch (int [] array, int key){
        int lowBound= 0;
        int upBound= array.length-1;

        while (upBound>=lowBound){
            int mid= (lowBound+upBound)/2;
            if(array[mid]>key){
                upBound=mid-1;
            } else if (array[mid]<key){
                lowBound=mid+1;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main (String [] args){
        //make sure array is sorted
        System.out.println(binarySearch(new int [] {1,2,3,4,5}, 2));
        System.out.println(binarySearch(new int [] {1,2,3,4,5}, -9));
        System.out.println(binarySearch(new int [] {1,2,3,4,5}, 5));
    }
}

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: