I. binary search method - (geek time record)

Binary search method can solve the problem, more tend to use hash table or binary tree. Dichotomy is more suitable for approximate search problems.

Error prone details:

• Termination conditions;
• The method of updating the upper and lower bounds of interval;
• Selection of return value;

import java.util.Scanner;
import java.util.Arrays;

public class BinaraySearch {

	public static int rank(int key,int[] a) {
		int lo=0;
		int hi=a.length-1;
		while(lo<=hi) {
			int mid=lo+(hi-lo)/2;
			if(key<a[mid]) hi=mid-1;
			else if(key>a[mid]) lo=mid+1;
			else return mid;
		}
		return -1;
	}
	
	public static int bssearch(int key,int[] a) {
		return bsearchInternally(key, a, 0, a.length-1);
	}
	private static int bsearchInternally(int key, int[] a, int low, int high) {
		// TODO Auto-generated method stub
		int mid = low + ((high - low)>>1);
		if(a[mid] == key) return mid;
		else if(a[mid] > key) {
			return bsearchInternally(key, a, low, mid -1);
		}else if(a[mid] < key) {
			return bsearchInternally(key, a, mid+1, high);
		}
		return 0;
	}
	//Variant 1 --- if there are repeated numbers in the sorted array, find the first equal number
	public static int bsearchQuestion1(int value, int[] a) {
		int low = 0;
		int high = a.length - 1;
		while(low <= high) {
			int mid = low + ((high - low)>>1);
			if(a[mid] < value) {
				low = mid +1;
			}else if(a[mid] > value) {
				high = mid - 1;
			}else {//Where changes have taken place
				if((mid == 0) || (a[mid - 1] != value)) return mid;//If the mid reaches 0, there must be no number in front of it. If the front and value are equal, modify high
				else high = mid - 1;
			}
		}
		return -1;
	}
	//Variant 2 --- if there are repeated numbers in the sorted array, find the last equal number
	public static int bsearchQuestion2(int value, int[] a) {
		int low = 0;
		int high = a.length - 1;
		while(low <= high) {
			int mid = low + ((high - low)>>1);
			if(a[mid] < value) {
				low = mid +1;
			}else if(a[mid] > value) {
				high = mid - 1;
			}else {//Where changes have taken place
				if((mid == a.length - 1) || (a[mid + 1] != value)) return mid;//If the mid reaches 0, there must be no number in front of it. If the front and value are equal, modify high
				else low = mid + 1;
			}
		}
		return -1;
	}
	//Variant 3 --- find the first number greater than or equal to the given value
	public static int bsearchQuestion3(int value, int[] a) {
		int low = 0;
		int high = a.length - 1;
		while(low <= high) {
			int mid = low + ((high - low)>>1);
			if(a[mid] < value) {
				low = mid + 1;
			}else {
				if((mid == 0) || (a[mid - 1] < value))return mid;
				else high = mid -1;
			}
		}
		return -1;
	}
	
	//Variant 4 --- find the last number less than or equal to the given value
	public static int bsearchQuestion4(int value, int[] a) {
		int low = 0;
		int high = a.length - 1;
		while(low <= high) {
			int mid = low + ((high - low)>>1);
			if(a[mid] < value) {
				low = mid + 1;
			}else {
				if((mid == a.length - 1) || (a[mid + 1] > value))return mid;
				else low = mid + 1;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//Standard input, read split and convert to int
		System.out.println("Input array:");
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine().toString();
		String arr[] = str.split(" ");
		int[] a = new int[arr.length];
		for(int j=0;j<=a.length-1;j++) {
			a[j] = Integer.parseInt(arr[j]);
			//System.out.print(a[j] + " ");
		}
		Arrays.sort(a);
		
		System.out.println("Enter the number to query");
		Scanner x=new Scanner(System.in);
		int number = x.nextInt();
		System.out.println(bsearchQuestion3(number,a));
	}

}

Thinking question: when a given array is a cyclic array, how to implement binary search algorithm;

The title corresponds to Leetcode33