Binary Search Algorithm

What is binary search?
Binary search is one of the searching algorithm used to find element in sorted array in Logarithmic running time complexity

Note: Binary search can only be applied in sorted array

Why binary search is better then linear search
Binary search has O(log(n)) logarithmic time complexity and linear search has O(n) linear time complexity

How Binary Search Work
Binary search use divide and conquer strategy to search element in given array. Binary search divide the searching area into exact half in each pass.

start : it store the value of starting index
end : it stores the value of ending index
mid : it stores the value of middle index

start = 0
end = array_length -1
mid = (start + end)/2 // but that's not good practice
(start + end) can sometime exceed the integer limit

mid = start + (end - start)/2 // this is the correct way

Suppose at first we have an array nums = { 1, 2, 4, 8, 10, 50, 70, 88, 100 } (note here array is sorted) and your target element is 70.
First check if middle element of array is equal to target or not. If it's equal then return middle index or mid. If not then check if target is smaller or bigger then middle element.
If target is smaller then middle element reduce the search space, end = mid -1. Now new search space is (start, mid -1).

If target is bigger the middle element reduce the search space, start = mid +1. Now new search space is (mid+1, end).

Hence, at each pass the search space will reduce into half until start <= end. If start became greater then end, the loop will break

Algorithm
Binary search in Java

import java.util.Arrays;  

public class BinarySearch {
    public static void main(String[] args) {

        int[] nums = { 1, 2, 3, 19, 29, 40, 60, 100 };
        int target = 40;

        System.out.println(Arrays.toString(nums));
        System.out.println(binarySearch(nums, target));
    }

    static int binarySearch(int[] nums, int target) {

        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {

            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }

        }

        return -1;
    }
}