13.3 Binary Search

The Binary search code checks if a value is present in an array. It assumes the array is already sorted least to greatest. It starts from the middle, and then redefines the middle based on whether the value is greater or less than it.
public class BinarySearch { // Returns index of x if it is present in arr[l.. // r], else return -1 public static int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the // middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not present // in array return -1; }
Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.