Find element in a sorted array

Binary Search in Sorted Array OR
Given a sorted array, Search a given element in array.

---

Searching an element in a sorted array.
You will be given a sorted array and an element, you need to find whether element is present in array or not.

Lets understand the problem statement graphically and it will be more clear,  
 

How to search an element in an array

---

Simple approach is to do linear search that is to check the element in array one by one and if we find the element then it is present else not.

In this approach, in worst case, we need to visit all the elements of the array atleast once to see if the element is present or not.

Example: if I tell you to search 23 in array [6, 9, 2, 1, 18, 15, 40, 23]
You need to first compare 23 with arr[0] (6), then with arr[1] (9), then with arr[2] (2) and so on till we encounter 23 which is present at last.

If you note here, we need to visit all the elements to see 23 is present or not, so time complexity of searching an element in this array is O(n) that is if there are n elements in array then we need to check "n" times.

Now, if the given array is sorted, can we search the element efficiently by reducing the time complexity?

---

As the array is sorted, we can use this property to search an element in sorted array.

This time, instead of searching element one by one, we can directly jump to middle element and see  if the element is matching with the given element,

1. If element to search is matching with the middle element then we found the element.


2. If element to search is less than the middle element then we need to search on sub array present on left side of middle element and ignore the right sub array.


3. If element to search is greater than the middle element then we need to search on sub array present on right side of middle element and ignore the left sub array.

If you notice, in each iteration, we jump to middle element and if we didn't got our element then we discard either left sub array or right sub array till we found our element.

It means we don't need to go through all the elements to search our element, instead we discard half elements in each iteration, so complexity for searching element in this approach is O(Log N).

This way of searching element where we discard half sub array each time is called Binary Search and time complexity of Binary Search is O(Log N).


Lets take an example of searching element 20 from an array, steps are explained in below image.

Java Program for Binary Search in Sorted Array.

---

package javabypatel;

public class BinarySearch {
    
    public static void main(String[] args) {
        int arr[] = new int[]{10, 20, 30, 40, 50, 60, 70, 80};
        System.out.println(binarySearch(arr, 10));
    }
     
    private static boolean binarySearch(int arr[], int dataToSearch){
        if(arr==null || arr.length<0){
            return false;
        }
         
        int start = 0;
        int end = arr.length-1;
         
        while(start <= end){
            int mid = start + (end-start)/2;
             
            if(dataToSearch == arr[mid]){ //Exact Match
                return true; 
                 
            }else if(dataToSearch < arr[mid]){ //Search on left
                end = mid-1;
            
            }else{  //Search on right
                start = mid+1;
            }
        }
        return false;
    }
}

You may also like to see

---

Count zeros in a row wise and column wise sorted matrix

---

Implement Stack using Queue

Find Largest and Smallest number in Array

Find middle element of a linked list

Union and Intersection of Two Sorted Arrays

Merge two sorted arrays in Java

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.