The **binary search algorithm** begins by comparing the target value to the value of the middle element of the **sorted array**. If the target value is equal to the middle element’s value, then the position is returned and the search is finished. If the target value is less than the middle element’s value, then the search continues on the lower half of the array; or if the target value is greater than the middle element’s value, then the search continues on the upper half of the array. This process continues, eliminating half of the elements, and comparing the target value to the value of the middle element of the remaining elements – until the target value is either found (and its associated element position is returned), or until the entire array has been searched (and “not found” is returned).The binary search algorithm can be classified as a divide and conquer search algorithm and executes in logarithmic time with O(logn) time complexity.

**Question :**

There is a sorted array of integers.You are given an element.Search the element in the array in 0(log n) complexity and return its index.

**Solution :**

The problem is solved in both iterative and recursive way.

**Algorithm :**

int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };

Suppose the element to be searched = 6

** Step 1 :** If the element to be searched is first compared with middle element.If it is equal to the middle element then return the middle element index.

** Step 2 :** If the element to be searched is greater than middle element search in the right sub array.If it is equal to less than middle element then search in left sub array.

** Step 3 :** If the element is not found then return -1 or print it is not found.

**Program :**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
package com.ai1tutorial.dsalgo.search; public class BinarySearch { public static void main(String[] args) { int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 }; binarySearchIter(arr, 6);// element to be searched is 6 if (binarySearchRecur(arr, 0, arr.length - 1, 6) == -1) { System.out.println("The number 6 is not present in the array"); } else { System.out.println("The number 6 is presnt at position " + (binarySearchRecur(arr, 0, arr.length - 1, 6) + 1)); } } private static void binarySearchIter(int[] arr, int number) { int lower = 0; int mid = 0; int upper = arr.length - 1; boolean flag = false; for (mid = (lower + upper) / 2; lower <= upper; mid = (lower + upper) / 2) { if (arr[mid] == number) { System.out.println("The number " + number + " is present at position " + (mid + 1)); flag = true; break; } if (arr[mid] > number) { upper = mid - 1; } else { lower = mid + 1; } } if (!flag) { System.out.println("The number " + number + " is not found in the array"); } } private static int binarySearchRecur(int[] arr, int lower, int upper, int number) { if (lower < upper) { int mid = lower + (upper - lower) / 2; if (arr[mid] == number) { return mid; } if (arr[mid] > number) { return binarySearchRecur(arr, lower, mid, number); } else { return binarySearchRecur(arr, mid + 1, upper, number); } } return -1; } } |

**Output:**

1 2 3 4 |
The number 6 is present at position 3 The number 6 is present at position 3 |