FilesExpand file tree

master

/

searchInsertPosition.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (48 loc) · 1.33 KB

master

/

searchInsertPosition.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (48 loc) · 1.33 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

// Source : https://oj.leetcode.com/problems/search-insert-position/

// Author : Hao Chen

// Date : 2014-06-22

/**********************************************************************************

*

* 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.

*

* Here are few examples.

* [1,3,5,6], 5 → 2

* [1,3,5,6], 2 → 1

* [1,3,5,6], 7 → 4

* [1,3,5,6], 0 → 0

*

*

**********************************************************************************/

#include <stdio.h>

int binary_search(int A[], int n, int key) {

int low = 0;

int high = n-1;

while (low <= high){

int mid = low +(high-low)/2;

if (A[mid] == key){

return mid;

}

if ( key> A[mid] ) {

low = mid+1;

}else{

high = mid-1;

}

}

return low;

}

int searchInsert(int A[], int n, int target) {

if (n==0) return n;

return binary_search(A, n, target);

}

int main()

{

int a[]={1,3,5,6};

printf("%d -> %d\n", 5, searchInsert(a, 4, 5));

printf("%d -> %d\n", 2, searchInsert(a, 4, 2));

printf("%d -> %d\n", 7, searchInsert(a, 4, 7));

printf("%d -> %d\n", 0, searchInsert(a, 4, 0));

return 0;

}