Binary search algorithm and example

🔍 Binary Search (Divide-and-Conquer Algorithm)

What problem are we solving?

When we have a sorted array, we often need to locate a specific value efficiently — for example, to find the index of a student ID or a product code.
Instead of scanning element by element like Linear Search (which takes O(n) time), Binary Search repeatedly divides the search space in half, achieving much faster performance.

---

🧠 How it works (step by step)

1. Precondition: The array must already be sorted (either ascending or descending).

2. Initialize two pointers:

   • start = 0 (beginning of the array)

   • end = arr.length - 1 (end of the array)

3. Find the middle index:
   mid = (start + end) / 2

4. Compare the middle element (arr[mid]) with the key you’re searching for:

   • If arr[mid] == key → ✅ Found → return mid

   • If key < arr[mid] → search left half → set end = mid - 1

   • If key > arr[mid] → search right half → set start = mid + 1

5. Repeat until start > end.
   If the loop ends with no match, the key isn’t present → return -1.

 

package com.vinod.test;


/**
 * Binary search use to find out the position of the elements for the given key.
 *
 * The Array should be either in ascending or decending order. 
 *
 *@authorvinodkariyathungalkumaran
 *
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 7, 9, 12, 16, 18 };
        System.out.println("Position of 5=" + getPositionUsingBinarySearch(arr, 5));

    }

    /**
     * Algorithm
     *
     *1) First get the array mid position, if mid position of the value equal to the search key will return that one
     *
     *2) Else if key is less the mid value our start value will be o and end value will be mid -1
     *
     *3) Else if the key is greater than the mid value we will mark our start value as mid value +1
     *
     * This activity we will do until the start and end values are equal.
     *
     *
     *@param arr
     *@param key
     *@return
     */
    public static int getPositionUsingBinarySearch(int[] arr, int key) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (key == arr[mid]) {
                return mid;
            }
            if (key < arr[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}