Binary Search in Java using Divide and Conquer

A binary search is a simplistic algorithm intended for finding the location of an item stored in a sorted list. 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.

Binary Search

When you run the program, the output will be:

Index of element is  6

Index of element is -1