Home | Tutorials | Articles | Videos | Products | Tools | Search
 Interviews | Open Source | Tag Cloud | Follow Us | Bookmark | Contact
 Data Structures > Search > Binary Search Non Recursive

# Binary Search Non Recursive

Binary search is faster when compared to Linear search. The pre condition for Binary Search to work is the elements of array should be sorted. Its time complexity is O(log n). It works as follows,

1. Get the middle element of list.
2. If search element is less than middle element then perform Step1 by passing first sub half (first element to middle element) as a list.
3. If search element is greater than middle element then perform Step1 by passing second sub half (middle element to last element) as a list.
4. If search element matches with middle element then search is finished.
This example shows binary search implementation using non recursive algorithm.

 File Name  : com/bethecoder/tutorials/ds/search/BinarySearchNonRecursive.java Author  : Sudhakar KV Email  : [email protected]

 ``` package com.bethecoder.tutorials.ds.search; import java.util.Arrays; public class BinarySearchNonRecursive {   /**    * @param args    */   public static void main(String[] args) {     int[] list = { 6, 5, 1, 8, 3, 9, 4, 0, 2, 7 };     //Make sure to sort the list if its not sorted already     Arrays.sort(list);     System.out.println("Sorted array : " + Arrays.toString(list));     //Binary Search     binarySearch(list, 2);     binarySearch(list, 8);     binarySearch(list, 12);   }   /**    * The precondition for binary search is the search list is sorted.    *     * @param list    * @param searchEle    * @return    */   public static int binarySearch(int[] sortedList, int searchEle) {     int index = binarySearch(sortedList, 0, sortedList.length - 1, searchEle);     System.out.println(searchEle + " found in array at index : " + index);     return index;   }   public static int binarySearch(int[] sortedList, int startIndex, int endIndex, int searchEle) {     while (startIndex <= endIndex) {       int midIndex = startIndex + (endIndex - startIndex)/2;       if (searchEle < sortedList[midIndex]) {         endIndex = midIndex - 1;       } else if (searchEle > sortedList[midIndex]) {         startIndex = midIndex + 1;       } else {         //means searchEle == sortedList[midIndex]         return midIndex;       }     }     return -1;   } }```

It gives the following output,
```Sorted array : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2 found in array at index : 2
8 found in array at index : 8
12 found in array at index : -1
```