Binary search in array in java using divide and conquer
Let
LIST be a list of elements that are sorted in nondecreasing 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 i^{th }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 7^{th} 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)