Binary search in array in java using divide and conquer

Posted By: Java Examples - 10:04 PM

Share

& Comment


Let LIST be a list of elements that are sorted in non-decreasing order. Consider the problem of determining whether a given element x is present in the list. If x is present, we return the value j for which LIST[j]=x. If it is not in the list just return -1. The search begins by comparing x w ith the element in the middle of the list. If x equals this element, the search terminates. If x is smaller than this element, then we need only search the left half. If x is bigger than the middle element, only the right half needs to be searched
            
   
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
Array of integers, named array, arranged in "ascending order"!!
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Index of array element

We will be searching for the integer  20 :
  •   First, find the middle of the array by adding the array subscript of the first value to the subscript of the last value and dividing by two:  (0 + 14) / 2 = 7   Integer division is used to arrive at the 7th subscript as the middle. ( we must work with integer subscripts.)
  • The 7th subscript holds the integer  16, which comes before 20.  We know that 20 will be in that portion of the array to the right of 16.  We now find the middle of the right portion of the array by using the same approach.  (8+14) / 2 = 11
  • The 11th subscript holds the integer 24  which comes after 20.  Now find the middle of the portion of the array to the right of 16, but to the left of 24. (8 + 10) / 2 = 9
  • The 9th subscript holds the integer 20.


Java version of the binary search is given below:
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package binarysearcharray;

/**
 *
 * @author ACHCHUTHAN
 */
public class BinarySearch {

    int[] array = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30};

    public int search(int key) {
        int l = 0;
        int r = array.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (key == array[mid]) {
                return mid;
            }
            if (key < array[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch b = new BinarySearch();
        for (int i = 2; i < 32; i += 2) {
            System.out.println("Search for element " + i );
            System.out.println("This element is found at " + b.search(i));
            System.out.println("=======+============+===============");
        }
    }
}



Output of this program :
run:
Search for element 2
This element is found at 0
=======+============+=======+==============
Search for element 4
This element is found at 1
=======+============+=======+==============
Search for element 6
This element is found at 2
=======+============+=======+==============
Search for element 8
This element is found at 3
=======+============+=======+==============
Search for element 10
This element is found at 4
=======+============+=======+==============
Search for element 12
This element is found at 5
=======+============+=======+==============
Search for element 14
This element is found at 6
=======+============+=======+==============
Search for element 16
This element is found at 7
=======+============+=======+==============
Search for element 18
This element is found at 8
=======+============+=======+==============
Search for element 20
This element is found at 9
=======+============+=======+==============
Search for element 22
This element is found at 10
=======+============+=======+==============
Search for element 24
This element is found at 11
=======+============+=======+==============
Search for element 26
This element is found at 12
=======+============+=======+==============
Search for element 28
This element is found at 13
=======+============+=======+==============
Search for element 30
This element is found at 14
=======+============+=======+==============
BUILD SUCCESSFUL (total time: 0 seconds)

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .