Binary Search

You have a big list of numbers and you want to search an element from it, how to do it?
Simplest approach would be to compare this number with all the elements from the list. In this case, if the element is the last element then we have to go through all the elements till we reach the element we want and what if it doesn't exist.

There are many searching algorithms to get it done efficiently, one of them is Binary Search.

In binary search :
Step 1. Sort the list of elements in ascending order
Step 2. Check the value of element that needs to be search (lets call this 'x') with the middle element (midElement) in the list.
Step 3. If the value of x is greater than midElement then the value is present in the right half of the array or else it is present in the left half of the array.
Step 4. Depending on the right or left half of the array, x will be compared. Lets assume it is present in left half, then the leftMidElement is compared with x and then Step 3 is repeated until we find the position for our element.

Below is the code for binary search :

private static int binarySearch(int list[], int leftIndex, int rightIndex,
            int x) {

        if (leftIndex <= rightIndex) {
            int midIdx = (leftIndex + (rightIndex)) / 2;
            if (x == list[midIdx])
                return midIdx;

            if (x > list[midIdx]) {
                leftIndex = midIdx + 1;
            } else if (x < list[midIdx]) {
                rightIndex = midIdx - 1;
            }
        }else{
            return -1;
        }
        return binarySearch(list, leftIndex, rightIndex, x);

    }

    public static void main(String arg[]) {
        int list[] = { 3, 5, 7, 15, 16, 22, 84 };
        int leftIndex = 0;
        int rightIndex = list.length;
        int position = binarySearch(list, leftIndex, rightIndex - 1, 7);
        if(position == -1){
            System.out.println("Value not found!!");
        }else{
            System.out.println("The position = " + position);   
        }
       
    }
 
In case of linear search the time complexity of the application is O(n) but in case of Binary Search it is O(logn);