Find the position to insert element in a sorted array

insertInSortedArray.java

// Java implementation of iterative Binary Search
class BinarySearch
{
	// Returns index of x if it is present in arr[], else
	// return -1
	int binarySearch(int arr[], int x)
	{
		if(x > arr[arr.length-1]) {
		    return arr.length; 
		}
		int l = 0, r = arr.length - 1;
		while (l <= r)
		{
			int m = l + (r-l)/2;

			// Check if x is present at mid
			if (arr[m] == x || ( (m == 0 || arr[m-1] < x )) && (m == (arr.length-1) || x < arr[m]))
				return m;

			// If x greater, ignore left half
			if (arr[m] < x)
				l = m + 1;

			// If x is smaller, ignore right half
			else
				r = m - 1;
		}

		// if we reach here, then element was not present
		return -1;
	}

	// Driver method to test above
	public static void main(String args[])
	{
		BinarySearch ob = new BinarySearch();
		int arr[] = {0, 5, 10, 15, 20};
		int n = arr.length;
		int x = -22;
		int result = ob.binarySearch(arr, x);
		if (result == -1)
			System.out.println("Element not present");
		else
			System.out.println("Element found at index "+result);
	}
}