Sorting and searching

The idea

Linear search examines candidates in sequence and works without sorted input. It can stop when a match appears, or finish without one. Binary search instead discards half of a sorted search interval after comparing its midpoint. The ordering requirement is essential: applying binary search to arbitrary data can miss an element that is present. Define what an absent result means before using it as an index.

Sorting builds an order that later operations can exploit. In insertion sort, the prefix before the current item is already sorted. Move larger prefix elements right, then place the saved item into the gap. Keep that saved value outside the shifting array positions so it is not overwritten during the process.

import java.util.Arrays;
public class Main {
  public static void main(String[] args) {
    int[] scores = {12, 3, 9, 6};
    Arrays.sort(scores);
    System.out.println(Arrays.toString(scores));
    System.out.println(Arrays.binarySearch(scores, 9));
  }
}

[3, 6, 9, 12]
2

After sorting, nine occupies index two. The search result is an index, not the stored value or a one-based position.