Binary Search

Given an sorted integer array - nums, and an integer - target. Find the first position of target in nums, return -1 if target doesn’t exist. 二分搜索算法的算法复杂度是log(n)，比线性算法好很多。不过前提是序列已经排好序了。面试的时候如果问到有没有比线性更好地算法，一般来说有两种，一种就是二分，一种就是hashmap(用空间来换时间)

如何搜搜？ Recursion or While-Loop?

递归

int binarySearch(int *array, int left, int right, int value) {
	if(left > right) {
		//value not found
		return -1;
	}

	int mid = left + (right - left)/2;
	if(array[mid] == value) {
		return mid;
	} else if (array[mid] < value) {
		return binarySearch(array, mid + 1, right, value);
	} else {
		return binarySearch(array, left, mid - 1, value);
	}
}

while循环

int binarySearch2(const int a[], const int size, const int val)
{
	int lower = 0;
	int upper = size - 1;

	while(lower < upper)
	{
		int i = lower + ((upper - lower) >> 1);//移位符号相当于除以2
		if (val ==  a[i]) {
			return i;
		} else if(val < a[i]) {
			upper = i - 1;
		} else {
			lower = i + 1;
		}
	}
	return -1;
}

Find i in a given sorted array that arr[i] == i

源代码地址

#include <iostream>
using namespace std;
int indexSearch(int *array, int left, int right) {
    if (left > right) {
        // value not found
        return -1;
    }

    int mid = right - (right - left) / 2;    
    if (array[mid] == mid) {
        return mid;
    } else if (array[mid] < mid) {
        return indexSearch(array, mid + 1, right);
    } else {
        return indexSearch(array, left, mid - 1);
    }
}
int main()
{
	int arr[9] = {-7,-2,0,3,7,9,10,12,13};
	cout << indexSearch(arr, 0, sizeof(arr)/sizeof(int)) << endl;//算法正确，返回3
	return 0;
}

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. LeetCode原题链接

/**
 * 使用while loop来做二分查找
 * @author luke
 *
 */
/**
 * 使用while loop来做二分查找
 * @author luke
 *
 */
public class Solution {
	public int searchInsert(int[] A, int target) {
		int begin = 0;
		int end = A.length - 1;
		while (begin <= end) {
			int mid = begin + (end - begin)/2;
			if (A[mid] == target) {
				return mid;
			}
			if (A[mid] > target) {
				end = mid - 1;

			} else {
				begin = mid + 1;
			}
		}
		//当需要寻找的数特别小的时候
		if (end == -1) {
			return 0;
		}

		if (A[end] < target)
		{
			return end + 1;
		} else {
			return end;
		}		
	}
	public static void main(String[] args) {
		//int nums[] = new int[4]; //也可以先这样声明，然后再赋值
		int nums[] = {1, 3, 5, 6};//Java声明数组的时候不能指定其长度
		Solution solution = new Solution();
		int index = solution.searchInsert(nums, 0);
		System.out.println(index + "\n");
	}
}

呃。。。Java和C++来回切换后发现连声明定义数组都不会了。。。囧。。。

Search in Rotated Sorted Array An array is sorted without duplicates. However, someone mysteriously shifted all the elements in this array(e.g. 1,2,3,4,5 -> 5,1,2,3,4). Implement a function to find an element in such array(return -1 if no such element). LeetCode原题链接这个数列具有局部有序的特性。

第一步：通过mid把数组分成两个半边
第二步：将两个子数组的各自头尾数据进行比较，确定哪一个是有序的
第三步：根据我需要搜索的哪个元素落在哪个半边，从而将范围折半源代码

int rotated_binary_search(int A[], int N, int key) {
  int L = 0;
  int R = N - 1;

  while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
    int M = L + ((R - L) >> 1);
    if (A[M] == key) return M;

    // the bottom half is sorted
    if (A[L] <= A[M]) {
      if (A[L] <= key && key < A[M])
        R = M - 1;
      else
        L = M + 1;
    }
    // the upper half is sorted
    else {
      if (A[M] < key && key <= A[R])
        L = M + 1;
      else
        R = M - 1;
    }
  }
  return -1;
}